Quake III Demo File Specifications

Quake III Arena Demo File Specifications

File formats: *.dm_66, *.dm_67, *.dm_68

Document Version 4

1. About

2. Sizebuf_t structure

3. Demofile format

4. MSG_ReadBits and MSG_WriteBits

5. Common MSG_* functions

6. Delta encoding of game structures

7. Huffman encoding

8. Server to Client commands

9. Operations with gameState_t

10. Parsing whole demo file

11. Thanks to

1. About

This document contains complete Quake III Arena Demo File specifications, useful for programmers working in C or C++ developing demo players/editors. It introduces demo message encoding/decoding routines that allow parsing and writing Quake III Arena Demo Files.

Note this code doesn’t provide full Quake III Arena network protocol support, as it uses much more encryption. All network-only stuff was removed from this document.

This code is redistributed under the terms of GNU General Public License:

Quake III *.dm_6? Demo Specifications

Based on Argus and Quake II source code

Also contains some stuff from Q3A SDK

This program is free software; you can redistribute it and/or

modify it under the terms of the GNU General Public License

as published by the Free Software Foundation; either version 2

of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,

but WITHOUT ANY WARRANTY; without even the implied warranty of

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License

along with this program; if not, write to the Free Software

Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

You can also download this example application (source code + binary):

http://skuller-vidnoe.narod.ru/downloads/dm_68.zip

It contains all source code present in this document and all necessary headers. The only thing this app does is dumping obituaries and some other info from a *.dm_68 file.

2. Sizebuf_t structure

All MSG_* functions operate with the sizebuf_t structure, which holds all necessary information about current buffer state and is used both when reading and writing bits to the buffer. Normally nothing outside MSG_* functions should modify this structure.

typedef struct sizebuf_s {

qboolean allowoverflow; // if false, do a Com_Error

qboolean overflowed; // set to true if the buffer size failed

qboolean uncompressed; // don't do Huffman encoding, write raw bytes

byte *data; // pointer to message buffer, set by MSG_Init

int maxsize; // size in bytes of message buffer, set by MSG_Init

int cursize; // number of bytes written to the buffer, set by MSG_WriteBits

int readcount; // number of bytes read from the buffer, set by MSG_ReadBits

int bit; // number of bits written to or read from the buffer

} sizebuf_t;

3. Demofile format

Actually Quake III Demo File is a version of server-to-client communication protocol, written to a disk in the following format:

<demo block> <...> <demo block> <end block>

Demo block structure:

Size, bytes	Description
4	Message sequence, <seq>
4	Message length, <msglen>
<msglen>	Message data

Demo is parsed until <seq> and <msglen> are not equal to -1 (end block), which indicates demofile EOF. <msglen> should be always less than MAX_MSGLEN.

#define MAX_MSGLEN 0x4000 // max length of demo message

Sample routine for demo file parsing:

FILE *demofile;

int demoMessageSequence; // used for delta decoding

=====================

Parse_NextDemoMessage

Read next message from demo file and parse it

Return qfalse if demo EOF reached or error occured

=====================

qboolean Parse_NextDemoMessage( void ) {

sizebuf_t msg;

byte buffer[MAX_MSGLEN];

int len;

int seq;

if( fread( &seq, 1, 4, demofile ) != 4 ) {

Com_Printf( "Demo file was truncated\n" );

return qfalse;

}

if( fread( &len, 1, 4, demofile ) != 4 ) {

Com_Printf( "Demo file was truncated\n" );

return qfalse;

}

if( seq == -1 || len == -1 ) {

return qfalse; // demo EOF reached

}

MSG_Init( &msg, buffer, sizeof( buffer ) );

demoMessageSequence = LittleLong( seq );

msg.cursize = LittleLong( len );

if( msg.cursize <= 0 || msg.cursize >= msg.maxsize ) {

Com_Error( ERR_DROP, "Illegal demo message length" );

}

if( fread( msg.data, 1, msg.cursize, demofile ) != msg.cursize ) {

Com_Printf( "Demo file was truncated\n" );

return qfalse;

}

Parse_DemoMessage( &msg ); // parse the message

return qtrue;

}

4. MSG_ReadBits and MSG_WriteBits

The basic functions for performing i/o operations on message data are MSG_WriteBits and MSG_ReadBits, which do Huffman encoding/decoding of the data bitstream using Huff_* code. If uncompressed flag is set on the sizebuf, then raw bytes are used, i.e. bits value is rounded to a full byte (q2-style). Currently this is not used when working with demo files.

============

MSG_WriteBits

============

void MSG_WriteBits( sizebuf_t *msg, int value, int bits ) {

int remaining;

int i;

byte *buf;

if( msg->maxsize - msg->cursize < 4 ) {

msg->overflowed = qtrue;

return;

}

if( !bits || bits < -31 || bits > 32 ) {

Com_Error( ERR_DROP, "MSG_WriteBits: bad bits %i", bits );

}

if( bits < 0 ) {

bits = -bits;

}

if( msg->uncompressed ) {

if( bits <= 8 ) {

buf = MSG_GetSpace( msg, 1 );

buf[0] = value;

} else if( bits <= 16 ) {

buf = MSG_GetSpace( msg, 2 );

buf[0] = value & 0xFF;

buf[1] = value >> 8;

} else if( bits <= 32 ) {

buf = MSG_GetSpace( msg, 4 );

buf[0] = value & 0xFF;

buf[1] = (value >> 8) & 0xFF;

buf[2] = (value >> 16) & 0xFF;

buf[3] = value >> 24;

}

return;

}

value &= 0xFFFFFFFFU >> (32 - bits);

remaining = bits & 7;

for( i=0 ; i<remaining ; i++ ) {

if( !(msg->bit & 7) ) {

msg->data[msg->bit >> 3] = 0;

}

msg->data[msg->bit >> 3] |= (value & 1) << (msg->bit & 7);

msg->bit++;

value >>= 1;

}

bits -= remaining;

if( bits > 0 ) {

for( i=0 ; i<(bits+7)>>3 ; i++ ) {

Huff_EmitByte( value & 255, msg->data, &msg->bit );

value >>= 8;

}

msg->cursize = (msg->bit >> 3) + 1;

}

============

MSG_ReadBits

============

int MSG_ReadBits( sizebuf_t *msg, int bits ) {

int i;

int val;

int bitmask = 0;

int remaining;

qboolean extend = qfalse;

if( !bits || bits < -31 || bits > 32 ) {

Com_Error( ERR_DROP, "MSG_ReadBits: bad bits %i", bits );

}

if( bits < 0 ) {

bits = -bits;

extend = qtrue;

}

if( msg->uncompressed ) {

if( bits <= 8 ) {

bitmask = (unsigned char)msg->data[msg->readcount];

msg->readcount++;

msg->bit += 8;

} else if( bits <= 16 ) {

bitmask = (unsigned short)(msg->data[msg->readcount]

+ (msg->data[msg->readcount+1] << 8));

msg->readcount += 2;

msg->bit += 16;

} else if( bits <= 32 ) {

bitmask = msg->data[msg->readcount]

+ (msg->data[msg->readcount+1] << 8)

+ (msg->data[msg->readcount+2] << 16)

+ (msg->data[msg->readcount+3] << 24);

msg->readcount += 4;

msg->bit += 32;

}

} else {

remaining = bits & 7;

for( i=0 ; i<remaining ; i++ ) {

val = msg->data[msg->bit >> 3] >> (msg->bit & 7);

msg->bit++;

bitmask |= (val & 1) << i;

}

for( i=0 ; i<bits-remaining ; i+=8 ) {

val = Huff_GetByteEx( msg->data, &msg->bit );

bitmask |= val << (i + remaining);

}

msg->readcount = (msg->bit >> 3) + 1;

}

if( extend ) {

if( bitmask & (1 << (bits - 1)) ) {

bitmask |= ~((1 << bits) - 1);

}

return bitmask;

}

There is a wrapper interface for writing/reading bytes, shorts and ints. It is implemented as macros and inline functions.

#define MSG_WriteByte(msg,c) MSG_WriteBits(msg,c,8)

#define MSG_WriteShort(msg,c) MSG_WriteBits(msg,c,16)

#define MSG_WriteSignedShort(msg,c) MSG_WriteBits(msg,c,-16)

#define MSG_WriteLong(msg,c) MSG_WriteBits(msg,c,32)

static ID_INLINE int MSG_ReadByte( sizebuf_t *msg ) {

int c = MSG_ReadBits( msg, 8 ) & 0xFF;

if( msg->readcount > msg->cursize ) {

return -1;

}

return c;

}

static ID_INLINE int MSG_ReadShort( sizebuf_t *msg ) {

int c = MSG_ReadBits( msg, 16 );

if( msg->readcount > msg->cursize ) {

return -1;

}

return c;

}

static ID_INLINE int MSG_ReadSignedShort( sizebuf_t *msg ) {

int c = MSG_ReadBits( msg, -16 );

if( msg->readcount > msg->cursize ) {

return -1;

}

return c;

}

static ID_INLINE int MSG_ReadLong( sizebuf_t *msg ) {

int c = MSG_ReadBits( msg, 32 );

if( msg->readcount > msg->cursize ) {

return -1;

}

return c;

}

5. Common MSG_* functions

// initialize sizebuf_t and associate it with specified buffer

void MSG_Init( sizebuf_t *msg, byte *buffer, int size );

// initialize sizebuf_t, associate it with specified buffer and set uncompressed flag

void MSG_InitRaw( sizebuf_t *msg, byte *buffer, int size );

// clear sizebuf_t, prepare it for writing and unset uncompressed flag

void MSG_Clear( sizebuf_t *msg );

// unset uncompressed flag for sizebuf_t

void MSG_SetBitstream( sizebuf_t *msg );

// strcat raw data to the sizebuf_t

void MSG_WriteRawData( sizebuf_t *msg, const void *data, int length );

// prepare sizebuf_t for writing and set uncompressed flag

void MSG_BeginWriting( sizebuf_t *msg );

// write data as bytes

void MSG_WriteData( sizebuf_t *msg, const void *data, int length );

// write string as bytes up to MAX_STRING_CHARS

void MSG_WriteString( sizebuf_t *msg, const char *string );

// write string as bytes up to BIG_INFO_STRING

void MSG_WriteBigString( sizebuf_t *msg, const char *string );

// prepare sizebuf_t for reading and set uncompressed flag

void MSG_BeginReading( sizebuf_t *msg );

// read data as bytes

void MSG_ReadData( sizebuf_t *msg, void *data, int len );

// read string as bytes up to MAX_STRING_CHARS

char *MSG_ReadString( sizebuf_t *msg );

// read string as bytes up to BIG_INFO_STRING

char *MSG_ReadBigString( sizebuf_t *msg );

============

MSG_GetSpace

============

static void *MSG_GetSpace( sizebuf_t *msg, int length ) {

void *data;

if( msg->cursize + length > msg->maxsize ) {

if( !msg->allowoverflow ) {

Com_Error( ERR_FATAL, "MSG_GetSpace: overflow without allowoverflow set" );

}

if( length > msg->maxsize ) {

Com_Error( ERR_FATAL, "MSG_GetSpace: %i is > full buffer size", length );

}

MSG_Clear( msg );

msg->overflowed = qtrue;

}

data = msg->data + msg->cursize;

msg->cursize += length;

msg->bit += length << 3;

return data;

}

============

MSG_Init

============

void MSG_Init( sizebuf_t *msg, byte *buffer, int size ) {

memset( msg, 0, sizeof( *msg ) );

msg->data = buffer;

msg->maxsize = size;

}

============

MSG_InitRaw

============

void MSG_InitRaw( sizebuf_t *msg, byte *buffer, int size ) {

memset( msg, 0, sizeof( *msg ) );

msg->data = buffer;

msg->maxsize = size;

msg->uncompressed = qtrue;

}

============

MSG_Clear

============

void MSG_Clear( sizebuf_t *msg ) {

msg->cursize = 0;

msg->overflowed = qfalse;

msg->uncompressed = qfalse;

msg->bit = 0;

}

============

MSG_SetBitstream

============

void MSG_SetBitstream( sizebuf_t *msg ) {

msg->uncompressed = qfalse;

}

============

MSG_WriteRawData

============

void MSG_WriteRawData( sizebuf_t *msg, const void *data, int length ) {

if( length > 0 ) {

memcpy( MSG_GetSpace( msg, length ), data, length );

}

============

MSG_BeginWriting

============

void MSG_BeginWriting( sizebuf_t *msg ) {

msg->uncompressed = qtrue;

msg->overflowed = 0;

msg->cursize = 0;

msg->bit = 0;

}

============

MSG_WriteData

============

void MSG_WriteData( sizebuf_t *msg, const void *data, int length ) {

int i;

for( i=0 ; i<length ; i++ ) {

MSG_WriteByte( msg, ((byte *)data)[i] );

}

============

MSG_WriteString

============

void MSG_WriteString( sizebuf_t *msg, const char *string ) {

char buffer[MAX_STRING_CHARS];

int i;

int len;

if( !string ) {

MSG_WriteByte( msg, 0 );

return;

}

len = strlen( string );

if( len >= sizeof( buffer ) ) {

Com_Printf( "MSG_WriteString: MAX_STRING_CHARS\n" );

MSG_WriteByte( msg, 0 );

return;

}

Q_strncpyz( buffer, string, sizeof( buffer ) );

for( i=0 ; i<len ; i++ ) {

if( buffer[i] > 127 ) {

buffer[i] = '.';

}

for( i=0 ; i<=len ; i++ ) {

MSG_WriteByte( msg, buffer[i] );

}

============

MSG_WriteString

============

void MSG_WriteBigString( sizebuf_t *msg, const char *string ) {

char buffer[BIG_INFO_STRING];

int i;

int len;

if( !string ) {

MSG_WriteByte( msg, 0 );

return;

}

len = strlen( string );

if( len >= sizeof( buffer ) ) {

Com_Printf( "MSG_WriteString: BIG_INFO_STRING\n" );

MSG_WriteByte( msg, 0 );

return;

}

Q_strncpyz( buffer, string, sizeof( buffer ) );

for( i=0 ; i<len ; i++ ) {

if( buffer[i] > 127 ) {

buffer[i] = '.';

}

for( i=0 ; i<=len ; i++ ) {

MSG_WriteByte( msg, buffer[i] );

}

============

MSG_BeginReading

============

void MSG_BeginReading( sizebuf_t *msg ) {

msg->readcount = 0;

msg->bit = 0;

msg->uncompressed = qtrue;

}

============

MSG_ReadData

============

void MSG_ReadData( sizebuf_t *msg, void *data, int len ) {

int i;

int c;

for( i=0 ; i<len ; i++ ) {

c = MSG_ReadByte( msg );

if( c == -1 ) {

break;

}

if( data ) {

((byte *)data)[i] = c;

}

============

MSG_ReadString

============

char *MSG_ReadString( sizebuf_t *msg ) {

static char string[MAX_STRING_CHARS];

int i;

int c;

for( i=0 ; i<sizeof( string )-1; i++ ) {

c = MSG_ReadByte( msg );

if( c == -1 || c == 0 ) {

break;

}

if( c == '%' || c > 127 ) {

c = '.';

}

string[i] = c;

}

string[i] = 0;

return string;

}

============

MSG_ReadBigString

============

char *MSG_ReadBigString( sizebuf_t *msg ) {

static char string[BIG_INFO_STRING];

int i;

int c;

for( i=0 ; i<sizeof( string )-1; i++ ) {

c = MSG_ReadByte( msg );

if( c == -1 || c == 0 ) {

break;

}

if( c == '%' || c > 127 ) {

c = '.';

}

string[i] = c;

}

string[i] = 0;

return string;

}

6. Delta encoding of game structures

For network bandwidth saving the following entityState_t and playerState_t structures are delta compressed when transmitted over the network:

// playerState_t is the information needed by both the client and server

// to predict player motion and actions

// nothing outside of pmove should modify these, or some degree of prediction error

// will occur

// you can't add anything to this without modifying the code in msg.c

// playerState_t is a full superset of entityState_t as it is used by players,

// so if a playerState_t is transmitted, the entityState_t can be fully derived

// from it.

typedef struct playerState_s {

int commandTime; // cmd->serverTime of last executed command

int pm_type;

int bobCycle; // for view bobbing and footstep generation

int pm_flags; // ducked, jump_held, etc

int pm_time;

vec3_t origin;

vec3_t velocity;

int weaponTime;

int gravity;

int speed;

int delta_angles[3]; // add to command angles to get view direction

// changed by spawns, rotating objects, and teleporters

int groundEntityNum; // ENTITYNUM_NONE = in air

int legsTimer; // don't change low priority animations until this runs out

int legsAnim; // mask off ANIM_TOGGLEBIT

int torsoTimer; // don't change low priority animations until this runs out

int torsoAnim; // mask off ANIM_TOGGLEBIT

int movementDir; // a number 0 to 7 that represents the reletive angle

// of movement to the view angle (axial and diagonals)

// when at rest, the value will remain unchanged

// used to twist the legs during strafing

vec3_t grapplePoint; // location of grapple to pull towards if PMF_GRAPPLE_PULL

int eFlags; // copied to entityState_t->eFlags

int eventSequence; // pmove generated events

int events[MAX_PS_EVENTS];

int eventParms[MAX_PS_EVENTS];

int externalEvent; // events set on player from another source

int externalEventParm;

int externalEventTime;

int clientNum; // ranges from 0 to MAX_CLIENTS-1

int weapon; // copied to entityState_t->weapon

int weaponstate;

vec3_t viewangles; // for fixed views

int viewheight;

// damage feedback

int damageEvent; // when it changes, latch the other parms

int damageYaw;

int damagePitch;

int damageCount;

int stats[MAX_STATS];

int persistant[MAX_PERSISTANT]; // stats that aren't cleared on death

int powerups[MAX_POWERUPS]; // level.time that the powerup runs out

int ammo[MAX_WEAPONS];

int generic1;

int loopSound;

int jumppad_ent; // jumppad entity hit this frame

// not communicated over the net at all

int ping; // server to game info for scoreboard

int pmove_framecount; // FIXME: don't transmit over the network

int jumppad_frame;

int entityEventSequence;

} playerState_t;

// if entityState->solid == SOLID_BMODEL, modelindex is an inline model number

#define SOLID_BMODEL 0xffffff

typedef enum {

TR_STATIONARY,

TR_INTERPOLATE, // non-parametric, but interpolate between snapshots

TR_LINEAR,

TR_LINEAR_STOP,

TR_SINE, // value = base + sin( time / duration ) * delta

TR_GRAVITY

} trType_t;

typedef struct {

trType_t trType;

int trTime;

int trDuration; // if non 0, trTime + trDuration = stop time

vec3_t trBase;

vec3_t trDelta; // velocity, etc

} trajectory_t;

// entityState_t is the information conveyed from the server

// in an update message about entities that the client will

// need to render in some way

// Different eTypes may use the information in different ways

// The messages are delta compressed, so it doesn't really matter if

// the structure size is fairly large

typedef struct entityState_s {

int number; // entity index

int eType; // entityType_t

int eFlags;

trajectory_t pos; // for calculating position

trajectory_t apos; // for calculating angles

int time;

int time2;

vec3_t origin;

vec3_t origin2;

vec3_t angles;

vec3_t angles2;

int otherEntityNum; // shotgun sources, etc

int otherEntityNum2;

int groundEntityNum; // -1 = in air

int constantLight; // r + (g<<8) + (b<<16) + (intensity<<24)

int loopSound; // constantly loop this sound

int modelindex;

int modelindex2;

int clientNum; // 0 to (MAX_CLIENTS - 1), for players and corpses

int frame;

int solid; // for client side prediction, trap_linkentity sets this properly

int event; // impulse events -- muzzle flashes, footsteps, etc

int eventParm;

// for players

int powerups; // bit flags

int weapon; // determines weapon and flash model, etc

int legsAnim; // mask off ANIM_TOGGLEBIT

int torsoAnim; // mask off ANIM_TOGGLEBIT

int generic1;

} entityState_t;

The following tables define offsets of each field in these structures and size of it (in bits):

======================================================================================

OFFSET TABLES FOR MAIN GAME STRUCTURES

If you want something from playerState_t or entityState structures to be

transmitted on the network, just insert a field into one of the following tables.

For network bandwidth saving, all fields are sorted in order from highest

modification frequency (during active gameplay) to lowest.

======================================================================================

typedef struct {

int offset;

int bits; // bits > 0 --> unsigned integer

// bits = 0 --> float value

// bits < 0 --> signed integer

} field_t;

// field declarations

#define PS_FIELD(n,b) { ((int)&(((playerState_t *)0)->n)), b }

#define ES_FIELD(n,b) { ((int)&(((entityState_t *)0)->n)), b }

// field data accessing

#define FIELD_INTEGER(s) (*(int *)((byte *)(s)+field->offset))

#define FIELD_FLOAT(s) (*(float *)((byte *)(s)+field->offset))

// playerState_t

static field_t psTable[] = {

PS_FIELD( commandTime, 32 ),

PS_FIELD( origin[0], 0 ),

PS_FIELD( origin[1], 0 ),

PS_FIELD( bobCycle, 8 ),

PS_FIELD( velocity[0], 0 ),

PS_FIELD( velocity[1], 0 ),

PS_FIELD( viewangles[1], 0 ),

PS_FIELD( viewangles[0], 0 ),

PS_FIELD( weaponTime, -16 ),

PS_FIELD( origin[2], 0 ),

PS_FIELD( velocity[2], 0 ),

PS_FIELD( legsTimer, 8 ),

PS_FIELD( pm_time, -16 ),

PS_FIELD( eventSequence, 16 ),

PS_FIELD( torsoAnim, 8 ),

PS_FIELD( movementDir, 4 ),

PS_FIELD( events[0], 8 ),

PS_FIELD( legsAnim, 8 ),

PS_FIELD( events[1], 8 ),

PS_FIELD( pm_flags, 16 ),

PS_FIELD( groundEntityNum, 10 ),

PS_FIELD( weaponstate, 4 ),

PS_FIELD( eFlags, 16 ),

PS_FIELD( externalEvent, 10 ),

PS_FIELD( gravity, 16 ),

PS_FIELD( speed, 16 ),

PS_FIELD( delta_angles[1], 16 ),

PS_FIELD( externalEventParm, 8 ),

PS_FIELD( viewheight, -8 ),

PS_FIELD( damageEvent, 8 ),

PS_FIELD( damageYaw, 8 ),

PS_FIELD( damagePitch, 8 ),

PS_FIELD( damageCount, 8 ),

PS_FIELD( generic1, 8 ),

PS_FIELD( pm_type, 8 ),

PS_FIELD( delta_angles[0], 16 ),

PS_FIELD( delta_angles[2], 16 ),

PS_FIELD( torsoTimer, 12 ),

PS_FIELD( eventParms[0], 8 ),

PS_FIELD( eventParms[1], 8 ),

PS_FIELD( clientNum, 8 ),

PS_FIELD( weapon, 5 ),

PS_FIELD( viewangles[2], 0 ),

PS_FIELD( grapplePoint[0], 0 ),

PS_FIELD( grapplePoint[1], 0 ),

PS_FIELD( grapplePoint[2], 0 ),

PS_FIELD( jumppad_ent, 10 ),

PS_FIELD( loopSound, 16 )

};

// entityState_t

static field_t esTable[] = {

ES_FIELD( pos.trTime, 32 ),

ES_FIELD( pos.trBase[0], 0 ),

ES_FIELD( pos.trBase[1], 0 ),

ES_FIELD( pos.trDelta[0], 0 ),

ES_FIELD( pos.trDelta[1], 0 ),

ES_FIELD( pos.trBase[2], 0 ),

ES_FIELD( apos.trBase[1], 0 ),

ES_FIELD( pos.trDelta[2], 0 ),

ES_FIELD( apos.trBase[0], 0 ),

ES_FIELD( event, 10 ),

ES_FIELD( angles2[1], 0 ),

ES_FIELD( eType, 8 ),

ES_FIELD( torsoAnim, 8 ),

ES_FIELD( eventParm, 8 ),

ES_FIELD( legsAnim, 8 ),

ES_FIELD( groundEntityNum, 10 ),

ES_FIELD( pos.trType, 8 ),

ES_FIELD( eFlags, 19 ),

ES_FIELD( otherEntityNum, 10 ),

ES_FIELD( weapon, 8 ),

ES_FIELD( clientNum, 8 ),

ES_FIELD( angles[1], 0 ),

ES_FIELD( pos.trDuration, 32 ),

ES_FIELD( apos.trType, 8 ),

ES_FIELD( origin[0], 0 ),

ES_FIELD( origin[1], 0 ),

ES_FIELD( origin[2], 0 ),

ES_FIELD( solid, 24 ),

ES_FIELD( powerups, 16 ),

ES_FIELD( modelindex, 8 ),

ES_FIELD( otherEntityNum2, 10 ),

ES_FIELD( loopSound, 8 ),

ES_FIELD( generic1, 8 ),

ES_FIELD( origin2[2], 0 ),

ES_FIELD( origin2[0], 0 ),

ES_FIELD( origin2[1], 0 ),

ES_FIELD( modelindex2, 8 ),

ES_FIELD( angles[0], 0 ),

ES_FIELD( time, 32 ),

ES_FIELD( apos.trTime, 32 ),

ES_FIELD( apos.trDuration, 32 ),

ES_FIELD( apos.trBase[2], 0 ),

ES_FIELD( apos.trDelta[0], 0 ),

ES_FIELD( apos.trDelta[1], 0 ),

ES_FIELD( apos.trDelta[2], 0 ),

ES_FIELD( time2, 32 ),

ES_FIELD( angles[2], 0 ),

ES_FIELD( angles2[0], 0 ),

ES_FIELD( angles2[2], 0 ),

ES_FIELD( constantLight, 32 ),

ES_FIELD( frame, 16 )

};

static const int psTableSize = sizeof( psTable ) / sizeof( psTable[0] );

static const int esTableSize = sizeof( esTable ) / sizeof( esTable[0] );

static const entityState_t nullEntityState;

static const playerState_t nullPlayerState;

Float values (or ‘vectors’) can be written as 32 bits or 13 bits. ‘Snapped’ vectors, i.e. floats without fractional part, are written as unsigned 13-bit integers for network bandwidth saving, if their values don’t exceed MAX_SNAPPED.

// snapped vectors are packed in 13 bits instead of 32

#define SNAPPED_BITS 13

#define MAX_SNAPPED (1<<SNAPPED_BITS)

Delta compressed structures are read/write using the following functions:

============

MSG_WriteDeltaEntity

If 'force' parm is false, this won't result any bits

emitted if entity didn't changed at all

'from' == NULL --> nodelta update

'to' == NULL --> entity removed

============

void MSG_WriteDeltaEntity( sizebuf_t *msg, const entityState_t *from, const entityState_t *to, qboolean force ) {

field_t *field;

int to_value;

int to_integer;

float to_float;

int maxFieldNum;

int i;

if( !to ) {

if( from ) {

MSG_WriteBits( msg, from->number, GENTITYNUM_BITS );

MSG_WriteBits( msg, 1, 1 );

}

return; // removed

}

if( to->number < 0 || to->number > MAX_GENTITIES ) {

Com_Error( ERR_DROP, "MSG_WriteDeltaEntity: Bad entity number: %i", to->number );

}

if( !from ) {

from = &nullEntityState; // nodelta update

}

// find last modified field in table

maxFieldNum = 0;

for( i=0, field=esTable ; i<esTableSize ; i++, field++ ) {

if( FIELD_INTEGER( from ) != FIELD_INTEGER( to ) ) {

maxFieldNum = i + 1;

}

if( !maxFieldNum ) {

if( !force ) {

return; // don't emit any bits at all

}

MSG_WriteBits( msg, to->number, GENTITYNUM_BITS );

MSG_WriteBits( msg, 0, 1 );

return; // unchanged

}

MSG_WriteBits( msg, to->number, GENTITYNUM_BITS );

MSG_WriteBits( msg, 0, 1 );

MSG_WriteBits( msg, 1, 1 );

MSG_WriteByte( msg, maxFieldNum );

// write all modified fields

for( i=0, field=esTable ; i<maxFieldNum ; i++, field++ ) {

to_value = FIELD_INTEGER( to );

if( FIELD_INTEGER( from ) == to_value ) {

MSG_WriteBits( msg, 0, 1 );

continue; // field unchanged

}

MSG_WriteBits( msg, 1, 1 );

if( !to_value ) {

MSG_WriteBits( msg, 0, 1 );

continue; // field set to zero

}

MSG_WriteBits( msg, 1, 1 );

if( field->bits ) {

MSG_WriteBits( msg, to_value, field->bits );

continue; // integer value

}

// figure out how to pack float value

to_float = FIELD_FLOAT( to );

to_integer = (int)to_float;

if( (float)to_integer == to_float

&& to_integer + MAX_SNAPPED/2 >= 0

&& to_integer + MAX_SNAPPED/2 < MAX_SNAPPED )

{

MSG_WriteBits( msg, 0, 1 ); // pack in 13 bits

MSG_WriteBits( msg, to_integer + MAX_SNAPPED/2, SNAPPED_BITS );

} else {

MSG_WriteBits( msg, 1, 1 ); // pack in 32 bits

MSG_WriteLong( msg, to_value );

}

============

MSG_ReadDeltaEntity

'from' == NULL --> nodelta update

'to' == NULL --> do nothing

============

void MSG_ReadDeltaEntity( sizebuf_t *msg, const entityState_t *from, entityState_t *to, int number ) {

field_t *field;

int maxFieldNum;

int i;

if( number < 0 || number >= MAX_GENTITIES ) {

Com_Error( ERR_DROP, "MSG_ReadDeltaEntity: Bad delta entity number: %i\n", number );

}

if( !to ) {

return;

}

if( MSG_ReadBits( msg, 1 ) ) {

memset( to, 0, sizeof( *to ) );

to->number = ENTITYNUM_NONE;

return; // removed

}

if( !from ) {

memset( to, 0, sizeof( *to ) ); // nodelta update

} else {

memcpy( to, from, sizeof( *to ) );

}

to->number = number;

if( !MSG_ReadBits( msg, 1 ) ) {

return; // unchanged

}

maxFieldNum = MSG_ReadByte( msg );

if( maxFieldNum > esTableSize ) {

Com_Error( ERR_DROP, "MSG_ReadDeltaEntity: maxFieldNum > esTableSize" );

}

// read all modified fields

for( i=0, field=esTable ; i<maxFieldNum ; i++, field++ ) {

if( !MSG_ReadBits( msg, 1 ) ) {

continue; // field unchanged

}

if( !MSG_ReadBits( msg, 1 ) ) {

FIELD_INTEGER( to ) = 0;

continue; // field set to zero

}

if( field->bits ) {

FIELD_INTEGER( to ) = MSG_ReadBits( msg, field->bits );

continue; // integer value

}

// read packed float value

if( !MSG_ReadBits( msg, 1 ) ) {

FIELD_FLOAT( to ) = (float)(MSG_ReadBits( msg, SNAPPED_BITS ) - MAX_SNAPPED/2);

} else {

FIELD_INTEGER( to ) = MSG_ReadLong( msg );

}

============

MSG_WriteDeltaPlayerstate

'from' == NULL --> nodelta update

'to' == NULL --> do nothing

============

void MSG_WriteDeltaPlayerstate( sizebuf_t *msg, const playerState_t *from, const playerState_t *to ) {

field_t *field;

int to_value;

float to_float;

int to_integer;

int maxFieldNum;

int statsMask;

int persistantMask;

int ammoMask;

int powerupsMask;

int i;

if( !to ) {

return;

}

if( !from ) {

from = &nullPlayerState; // nodelta update

}

// find last modified field in table

maxFieldNum = 0;

for( i=0, field=psTable ; i<psTableSize ; i++, field++ ) {

if( FIELD_INTEGER( from ) != FIELD_INTEGER( to ) ) {

maxFieldNum = i + 1;

}

MSG_WriteByte( msg, maxFieldNum );

// write all modified fields

for( i=0, field=psTable ; i<maxFieldNum ; i++, field++ ) {

to_value = FIELD_INTEGER( to );

if( FIELD_INTEGER( from ) == to_value ) {

MSG_WriteBits( msg, 0, 1 );

continue; // field unchanged

}

MSG_WriteBits( msg, 1, 1 );

if( field->bits ) {

MSG_WriteBits( msg, to_value, field->bits );

continue; // integer value

}

// figure out how to pack float value

to_float = FIELD_FLOAT( to );

to_integer = (int)to_float;

if( (float)to_integer == to_float

&& to_integer + MAX_SNAPPED/2 >= 0

&& to_integer + MAX_SNAPPED/2 < MAX_SNAPPED )

{

MSG_WriteBits( msg, 0, 1 ); // pack in 13 bits

MSG_WriteBits( msg, to_integer + MAX_SNAPPED/2, SNAPPED_BITS );

} else {

MSG_WriteBits( msg, 1, 1 ); // pack in 32 bits

MSG_WriteLong( msg, to_value );

}

// find modified arrays

statsMask = 0;

for( i=0 ; i<MAX_STATS ; i++ ) {

if( from->stats[i] != to->stats[i] ) {

statsMask |= (1 << i);

}

persistantMask = 0;

for( i=0 ; i<MAX_PERSISTANT ; i++ ) {

if( from->persistant[i] != to->persistant[i] ) {

persistantMask |= (1 << i);

}

ammoMask = 0;

for( i=0 ; i<MAX_WEAPONS ; i++ ) {

if( from->ammo[i] != to->ammo[i] ) {

ammoMask |= (1 << i);

}

powerupsMask = 0;

for( i=0 ; i<MAX_POWERUPS ; i++ ) {

if( from->powerups[i] != to->powerups[i] ) {

powerupsMask |= (1 << i);

}

if( !statsMask && !persistantMask && !ammoMask && !powerupsMask ) {

MSG_WriteBits( msg, 0, 1 );

return; // no arrays modified

}

// write all modified arrays

MSG_WriteBits( msg, 1, 1 );

// PS_STATS

if( statsMask ) {

MSG_WriteBits( msg, 1, 1 );

MSG_WriteShort( msg, statsMask );

for( i=0 ; i<MAX_STATS ; i++ ) {

if( statsMask & (1 << i) ) {

MSG_WriteSignedShort( msg, to->stats[i] );

}

} else {

MSG_WriteBits( msg, 0, 1 ); // unchanged

}

// PS_PERSISTANT

if( persistantMask ) {

MSG_WriteBits( msg, 1, 1 );

MSG_WriteShort( msg, persistantMask );

for( i=0 ; i<MAX_PERSISTANT ; i++ ) {

if( persistantMask & (1 << i) ) {

MSG_WriteSignedShort( msg, to->persistant[i] );

}

} else {

MSG_WriteBits( msg, 0, 1 ); // unchanged

}

// PS_AMMO

if( ammoMask ) {

MSG_WriteBits( msg, 1, 1 );

MSG_WriteShort( msg, ammoMask );

for( i=0 ; i<MAX_WEAPONS ; i++ ) {

if( ammoMask & (1 << i) ) {

MSG_WriteShort( msg, to->ammo[i] );

}

} else {

MSG_WriteBits( msg, 0, 1 ); // unchanged

}

// PS_POWERUPS

if( powerupsMask ) {

MSG_WriteBits( msg, 1, 1 );

MSG_WriteShort( msg, powerupsMask );

for( i=0 ; i<MAX_POWERUPS ; i++ ) {

if( powerupsMask & (1 << i) ) {

MSG_WriteLong( msg, to->powerups[i] ); // WARNING: powerups use 32 bits, not 16

}

} else {

MSG_WriteBits( msg, 0, 1 ); // unchanged

}

============

MSG_ReadDeltaPlayerstate

'from' == NULL --> nodelta update

'to' == NULL --> do nothing

============

void MSG_ReadDeltaPlayerstate( sizebuf_t *msg, const playerState_t *from, playerState_t *to ) {

field_t *field;

int maxFieldNum;

int bitmask;

int i;

if( !to ) {

return;

}

if( !from ) {

memset( to, 0, sizeof( *to ) ); // nodelta update

} else {

memcpy( to, from, sizeof( *to ) );

}

maxFieldNum = MSG_ReadByte( msg );

if( maxFieldNum > psTableSize ) {

Com_Error( ERR_DROP, "MSG_ReadDeltaPlayerstate: maxFieldNum > psTableSize" );

}

// read all modified fields

for( i=0, field=psTable ; i<maxFieldNum ; i++, field++ ) {

if( !MSG_ReadBits( msg, 1 ) ) {

continue; // field unchanged

}

if( field->bits ) {

FIELD_INTEGER( to ) = MSG_ReadBits( msg, field->bits );

continue; // integer value

}

// read packed float value

if( !MSG_ReadBits( msg, 1 ) ) {

FIELD_FLOAT( to ) = (float)(MSG_ReadBits( msg, SNAPPED_BITS ) - MAX_SNAPPED/2);

} else {

FIELD_INTEGER( to ) = MSG_ReadLong( msg );

}

// read all modified arrays

if( !MSG_ReadBits( msg, 1 ) ) {

return; // no arrays modified

}

// PS_STATS

if( MSG_ReadBits( msg, 1 ) ) {

bitmask = MSG_ReadShort( msg );

for( i=0 ; i<MAX_STATS ; i++ ) {

if( bitmask & (1 << i) ) {

to->stats[i] = MSG_ReadSignedShort( msg ); // PS_STATS can be negative

}

// PS_PERSISTANT

if( MSG_ReadBits( msg, 1 ) ) {

bitmask = MSG_ReadShort( msg );

for( i=0 ; i<MAX_PERSISTANT ; i++ ) {

if( bitmask & (1 << i) ) {

to->persistant[i] = MSG_ReadSignedShort( msg ); // PS_PERSISTANT can be negative

}

// PS_AMMO

if( MSG_ReadBits( msg, 1 ) ) {

bitmask = MSG_ReadShort( msg );

for( i=0 ; i<MAX_WEAPONS ; i++ ) {

if( bitmask & (1 << i) ) {

to->ammo[i] = MSG_ReadShort( msg );

}

// PS_POWERUPS

if( MSG_ReadBits( msg, 1 ) ) {

bitmask = MSG_ReadShort( msg );

for( i=0 ; i<MAX_POWERUPS ; i++ ) {

if( bitmask & (1 << i) ) {

to->powerups[i] = MSG_ReadLong( msg ); // WARNING: powerups use 32 bits, not 16

}

7. Huffman encoding

The following routines do Huffman encoding/decoding. Note that you have to do a Huff_Init call before using any MSG_* functions.

// huff.c - Huffman compression routines for data bitstream

#define VALUE(a) ((int )(a))

#define NODE(a) ((void *)(a))

#define NODE_START NODE( 1)

#define NODE_NONE NODE(256)

#define NODE_NEXT NODE(257)

#define HUFF_TREE_SIZE 7175

typedef void *tree_t[HUFF_TREE_SIZE];

// pre-defined frequency counts for all bytes [0..255]

static int huffCounts[256] = {

0x3D1CB, 0x0A0E9, 0x01894, 0x01BC2, 0x00E92, 0x00EA6, 0x017DE, 0x05AF3,

0x08225, 0x01B26, 0x01E9E, 0x025F2, 0x02429, 0x0436B, 0x00F6D, 0x006F2,

0x02060, 0x00644, 0x00636, 0x0067F, 0x0044C, 0x004BD, 0x004D6, 0x0046E,

0x006D5, 0x00423, 0x004DE, 0x0047D, 0x004F9, 0x01186, 0x00AF5, 0x00D90,

0x0553B, 0x00487, 0x00686, 0x0042A, 0x00413, 0x003F4, 0x0041D, 0x0042E,

0x006BE, 0x00378, 0x0049C, 0x00352, 0x003C0, 0x0030C, 0x006D8, 0x00CE0,

0x02986, 0x011A2, 0x016F9, 0x00A7D, 0x0122A, 0x00EFD, 0x0082D, 0x0074B,

0x00A18, 0x0079D, 0x007B4, 0x003AC, 0x0046E, 0x006FC, 0x00686, 0x004B6,

0x01657, 0x017F0, 0x01C36, 0x019FE, 0x00E7E, 0x00ED3, 0x005D4, 0x005F4,

0x008A7, 0x00474, 0x0054B, 0x003CB, 0x00884, 0x004E0, 0x00530, 0x004AB,

0x006EA, 0x00436, 0x004F0, 0x004F2, 0x00490, 0x003C5, 0x00483, 0x004A2,

0x00543, 0x004CC, 0x005F9, 0x00640, 0x00A39, 0x00800, 0x009F2, 0x00CCB,

0x0096A, 0x00E01, 0x009C8, 0x00AF0, 0x00A73, 0x01802, 0x00E4F, 0x00B18,

0x037AD, 0x00C5C, 0x008AD, 0x00697, 0x00C88, 0x00AB3, 0x00DB8, 0x012BC,

0x00FFB, 0x00DBB, 0x014A8, 0x00FB0, 0x01F01, 0x0178F, 0x014F0, 0x00F54,

0x0131C, 0x00E9F, 0x011D6, 0x012C7, 0x016DC, 0x01900, 0x01851, 0x02063,

0x05ACB, 0x01E9E, 0x01BA1, 0x022E7, 0x0153D, 0x01183, 0x00E39, 0x01488,

0x014C0, 0x014D0, 0x014FA, 0x00DA4, 0x0099A, 0x0069E, 0x0071D, 0x00849,

0x0077C, 0x0047D, 0x005EC, 0x00557, 0x004D4, 0x00405, 0x004EA, 0x00450,

0x004DD, 0x003EE, 0x0047D, 0x00401, 0x004D9, 0x003B8, 0x00507, 0x003E5,

0x006B1, 0x003F1, 0x004A3, 0x0036F, 0x0044B, 0x003A1, 0x00436, 0x003B7,

0x00678, 0x003A2, 0x00481, 0x00406, 0x004EE, 0x00426, 0x004BE, 0x00424,

0x00655, 0x003A2, 0x00452, 0x00390, 0x0040A, 0x0037C, 0x00486, 0x003DE,

0x00497, 0x00352, 0x00461, 0x00387, 0x0043F, 0x00398, 0x00478, 0x00420,

0x00D86, 0x008C0, 0x0112D, 0x02F68, 0x01E4E, 0x00541, 0x0051B, 0x00CCE,

0x0079E, 0x00376, 0x003FF, 0x00458, 0x00435, 0x00412, 0x00425, 0x0042F,

0x005CC, 0x003E9, 0x00448, 0x00393, 0x0041C, 0x003E3, 0x0042E, 0x0036C,

0x00457, 0x00353, 0x00423, 0x00325, 0x00458, 0x0039B, 0x0044F, 0x00331,

0x0076B, 0x00750, 0x003D0, 0x00349, 0x00467, 0x003BC, 0x00487, 0x003B6,

0x01E6F, 0x003BA, 0x00509, 0x003A5, 0x00467, 0x00C87, 0x003FC, 0x0039F,

0x0054B, 0x00300, 0x00410, 0x002E9, 0x003B8, 0x00325, 0x00431, 0x002E4,

0x003F5, 0x00325, 0x003F0, 0x0031C, 0x003E4, 0x00421, 0x02CC1, 0x034C0

};

// static Huffman tree

static tree_t huffTree;

// received from MSG_* code

static int huffBitPos;

======================================================================================

HUFFMAN TREE CONSTRUCTION

======================================================================================

============

Huff_PrepareTree

============

static ID_INLINE void Huff_PrepareTree( tree_t tree ) {

void **node;

memset( tree, 0, sizeof( tree_t ) );

// create first node

node = &tree[263];

VALUE( tree[0] )++;

node[7] = NODE_NONE;

tree[2] = node;

tree[3] = node;

tree[4] = node;

tree[261] = node;

}

============

Huff_GetNode

============

static void **Huff_GetNode( void **tree ) {

void **node;

int value;

node = tree[262];

if( !node ) {

value = VALUE( tree[1] )++;

node = &tree[value + 6407];

return node;

}

tree[262] = node[0];

return node;

}

============

Huff_Swap

============

static void Huff_Swap( void **tree1, void **tree2, void **tree3 ) {

void **a, **b;

a = tree2[2];

if( a ) {

if( a[0] == tree2 ) {

a[0] = tree3;

} else {

a[1] = tree3;

}

} else {

tree1[2] = tree3;

}

b = tree3[2];

if( b ) {

if( b[0] == tree3 ) {

b[0] = tree2;

tree2[2] = b;

tree3[2] = a;

return;

}

b[1] = tree2;

tree2[2] = b;

tree3[2] = a;

return;

}

tree1[2] = tree2;

tree2[2] = NULL;

tree3[2] = a;

}

============

Huff_SwapTrees

============

static void Huff_SwapTrees( void **tree1, void **tree2 ) {

void **temp;

temp = tree1[3];

tree1[3] = tree2[3];

tree2[3] = temp;

temp = tree1[4];

tree1[4] = tree2[4];

tree2[4] = temp;

if( tree1[3] == tree1 ) {

tree1[3] = tree2;

}

if( tree2[3] == tree2 ) {

tree2[3] = tree1;

}

temp = tree1[3];

if( temp ) {

temp[4] = tree1;

}

temp = tree2[3];

if( temp ) {

temp[4] = tree2;

}

temp = tree1[4];

if( temp ) {

temp[3] = tree1;

}

temp = tree2[4];

if( temp ) {

temp[3] = tree2;

}

============

Huff_DeleteNode

============

static void Huff_DeleteNode( void **tree1, void **tree2 ) {

tree2[0] = tree1[262];

tree1[262] = tree2;

}

============

Huff_IncrementFreq_r

============

static void Huff_IncrementFreq_r( void **tree1, void **tree2 ) {

void **a, **b;

if( !tree2 ) {

return;

}

a = tree2[3];

if( a && a[6] == tree2[6] ) {

b = tree2[5];

if( b[0] != tree2[2] ) {

Huff_Swap( tree1, b[0], tree2 );

}

Huff_SwapTrees( b[0], tree2 );

}

a = tree2[4];

if( a && a[6] == tree2[6] ) {

b = tree2[5];

b[0] = a;

} else {

a = tree2[5];

a[0] = 0;

Huff_DeleteNode( tree1, tree2[5] );

}

VALUE( tree2[6] )++;

a = tree2[3];

if( a && a[6] == tree2[6] ) {

tree2[5] = a[5];

} else {

a = Huff_GetNode( tree1 );

tree2[5] = a;

a[0] = tree2;

}

if( tree2[2] ) {

Huff_IncrementFreq_r( tree1, tree2[2] );

if( tree2[4] == tree2[2] ) {

Huff_SwapTrees( tree2, tree2[2] );

a = tree2[5];

if( a[0] == tree2 ) {

a[0] = tree2[2];

}

============

Huff_AddReference

Insert 'ch' into the tree or increment it's frequency

============

static void Huff_AddReference( void **tree, int ch ) {

void **a, **b, **c, **d;

int value;

ch &= 255;

if( tree[ch + 5] ) {

Huff_IncrementFreq_r( tree, tree[ch + 5] );

return; // already added

}

value = VALUE( tree[0] )++;

b = &tree[value * 8 + 263];

value = VALUE( tree[0] )++;

a = &tree[value * 8 + 263];

a[7] = NODE_NEXT;

a[6] = NODE_START;

d = tree[3];

a[3] = d[3];

if( a[3] ) {

d = a[3];

d[4] = a;

d = a[3];

if( d[6] == NODE_START ) {

a[5] = d[5];

} else {

d = Huff_GetNode( tree );

a[5] = d;

d[0] = a;

}

} else {

d = Huff_GetNode( tree );

a[5] = d;

d[0] = a;

}

d = tree[3];

d[3] = a;

a[4] = tree[3];

b[7] = NODE( ch );

b[6] = NODE_START;

d = tree[3];

b[3] = d[3];

if( b[3] ) {

d = b[3];

d[4] = b;

if( d[6] == NODE_START ) {

b[5] = d[5];

} else {

d = Huff_GetNode( tree );

b[5] = d;

d[0] = a;

}

} else {

d = Huff_GetNode( tree );

b[5] = d;

d[0] = b;

}

d = tree[3];

d[3] = b;

b[4] = tree[3];

b[1] = NULL;

b[0] = NULL;

d = tree[3];

c = d[2];

if( c ) {

if( c[0] == tree[3] ) {

c[0] = a;

} else {

c[1] = a;

}

} else {

tree[2] = a;

}

a[1] = b;

d = tree[3];

a[0] = d;

a[2] = d[2];

b[2] = a;

d = tree[3];

d[2] = a;

tree[ch + 5] = b;

Huff_IncrementFreq_r( tree, a[2] );

}

======================================================================================

BITSTREAM I/O

======================================================================================

============

Huff_EmitBit

Put one bit into buffer

============

static ID_INLINE void Huff_EmitBit( int bit, byte *buffer ) {

if( !(huffBitPos & 7) ) {

buffer[huffBitPos >> 3] = 0;

}

buffer[huffBitPos >> 3] |= bit << (huffBitPos & 7);

huffBitPos++;

}

============

Huff_GetBit

Read one bit from buffer

============

static ID_INLINE int Huff_GetBit( byte *buffer ) {

int bit;

bit = buffer[huffBitPos >> 3] >> (huffBitPos & 7);

huffBitPos++;

return (bit & 1);

}

============

Huff_EmitPathToByte

============

static ID_INLINE void Huff_EmitPathToByte( void **tree, void **subtree, byte *buffer ) {

if( tree[2] ) {

Huff_EmitPathToByte( tree[2], tree, buffer );

}

if( !subtree ) {

return;

}

// emit tree walking control bits

if( tree[1] == subtree ) {

Huff_EmitBit( 1, buffer );

} else {

Huff_EmitBit( 0, buffer );

}

============

Huff_GetByteFromTree

Get one byte using dynamic or static tree

============

static ID_INLINE int Huff_GetByteFromTree( void **tree, byte *buffer ) {

if( !tree ) {

return 0;

}

// walk through the tree until we get a value

while( tree[7] == NODE_NEXT ) {

if( !Huff_GetBit( buffer ) ) {

tree = tree[0];

} else {

tree = tree[1];

}

if( !tree ) {

return 0;

}

return VALUE( tree[7] );

}

======================================================================================

PUBLIC INTERFACE

======================================================================================

============

Huff_EmitByte

============

void Huff_EmitByte( int ch, byte *buffer, int *count ) {

huffBitPos = *count;

Huff_EmitPathToByte( huffTree[ch + 5], NULL, buffer );

*count = huffBitPos;

}

============

Huff_GetByte

============

int Huff_GetByte( byte *buffer, int *count ) {

int ch;

huffBitPos = *count;

ch = Huff_GetByteFromTree( huffTree[2], buffer );

*count = huffBitPos;

return ch;

}

============

Huff_Init

============

void Huff_Init( void ) {

int i, j;

// build empty tree

Huff_PrepTreeComp( huffTree );

// add all pre-defined byte references

for( i=0 ; i<256 ; i++ ) {

for( j=0 ; j<huffCounts[i] ; j++ ) {

Huff_AddReference( huffTree, i );

}

8. Server to Client commands

SerVer to Client commands (SVC_*) are hints to the client how to parse data stream received from server. There are 8 SVC_* types, but only 6 of them are used in demo files.

// possible server to client commands

typedef enum svc_ops_e {

SVC_BAD, // not used in demos

SVC_NOP, // not used in demos

SVC_GAMESTATE,

SVC_CONFIGSTRING, // only inside gameState

SVC_BASELINE, // only inside gameState

SVC_SERVERCOMMAND,

SVC_DOWNLOAD, // not used in demos

SVC_SNAPSHOT,

SVC_EOM

} svc_ops_t;

SVC_BAD – zero command, should never appear in network messages and demos

SVC_NOP – No OPeration command, should never appear in demos

SVC_GAMESTATE – received before each level start, contains configStrings and baselines

SVC_CONFIGSTRING, SVC_BASELINE – appear only inside gameState

SVC_SERVERCOMMAND – reliable text command to be processed by the client

SVC_DOWNLOAD – should never appear in demos

SVC_SNAPSHOT – contains delta compressed updates of playerState and entityStates

SVC_EOM – indicates End Of Message, also used inside gameState

Each demo message should contain either SVC_GAMESTATE or SVC_SNAPSHOT, but never them both and never no one of them.

9. Operations with gameState_t

#define MAX_CONFIGSTRINGS 1024

// these are the only configstrings that the system reserves, all the

// other ones are strictly for servergame to clientgame communication

#define CS_SERVERINFO 0 // an info string with all the serverinfo cvars

#define CS_SYSTEMINFO 1 // an info string for server system to client system configuration (timescale, etc)

#define RESERVED_CONFIGSTRINGS 2 // game can't modify below this, only the system can

#define MAX_GAMESTATE_CHARS 16000

typedef struct {

int stringOffsets[MAX_CONFIGSTRINGS];

char stringData[MAX_GAMESTATE_CHARS];

int dataCount;

} gameState_t;

gameState_t structure is used to hold all configStrings in a single text buffer. Because configStrings can be up to BIG_INFO_STRING chars, it would be better to use 20100 bytes of gameState_t instead of 8388608 bytes of static array of configStrings.

The following functions allow inserting and fetching configStrings from gameState_t:

============

Com_AppendToGameState

============

static void Com_AppendToGameState( gameState_t *gameState, int index, const char *configString ) {

int len;

if( !configString || !(len=strlen( configString )) ) {

return;

}

if( gameState->dataCount + len + 2 >= MAX_GAMESTATE_CHARS ) {

Com_Error( ERR_DROP, "Com_AppendToGameState: MAX_GAMESTATE_CHARS" );

}

gameState->stringOffsets[index] = gameState->dataCount + 1;

strcpy( &gameState->stringData[gameState->dataCount + 1], configString );

gameState->dataCount += len + 1;

}

============

Com_InsertIntoGameState

============

void Com_InsertIntoGameState( gameState_t *gameState, int index, const char *configString ) {

char *strings[MAX_CONFIGSTRINGS];

int ofs;

int i;

if( index < 0 || index >= MAX_CONFIGSTRINGS ) {

Com_Error( ERR_DROP, "Com_InsertIntoGameState: bad index %i", index );

}

if( !gameState->stringOffsets[index] ) {

// just append to the end of gameState

Com_AppendToGameState( gameState, index, configString );

return;

}

// resort gameState

for( i=0 ; i<MAX_CONFIGSTRINGS ; i++ ) {

ofs = gameState->stringOffsets[i];

if( !ofs ) {

strings[i] = NULL;

} else if( i == index ) {

strings[i] = CopyString( configString );

} else {

strings[i] = CopyString( &gameState->stringData[ofs] );

}

memset( gameState, 0, sizeof( *gameState ) );

for( i=0 ; i<MAX_CONFIGSTRINGS ; i++ ) {

if( strings[i] ) {

Com_AppendToGameState( gameState, i, strings[i] );

Z_Free( strings[i] );

}

============

Com_GetStringFromGameState

============

char *Com_GetStringFromGameState( gameState_t *gameState, int index ) {

int ofs;

if( index < 0 || index >= MAX_CONFIGSTRINGS ) {

Com_Error( ERR_DROP, "Com_GetStringFromGameState: bad index %i", index );

}

ofs = gameState->stringOffsets[index ];

if( !ofs ) {

return "";

}

return &gameState->stringData[ofs];

}

10. Parsing whole demo file

// sizes of misc circular buffers in client and server system

// for delta compression of snapshots

#define MAX_SNAPSHOTS 32

#define SNAPSHOT_MASK (MAX_SNAPSHOTS-1)

// for keeping reliable text commands not acknowledged by receiver yet

#define MAX_SERVERCMDS 64

#define SERVERCMD_MASK (MAX_SERVERCMDS-1)

// for keeping all entityStates for delta encoding

#define MAX_PARSE_ENTITIES (MAX_GENTITIES*2)

#define PARSE_ENTITIES_MASK (MAX_PARSE_ENTITIES-1)

// max number of entityState_t present in a single update

#define MAX_ENTITIES_IN_SNAPSHOT 256

typedef struct {

qboolean valid;

int seq; // die seqeunc number des snapshots

int deltaSeq;

int snapFlags; // SNAPFLAG_RATE_DELAYED, etc

int serverTime; // server time the message is valid for (in msec)

byte areamask[MAX_MAP_AREA_BYTES]; // portalarea visibility bits

playerState_t ps; // complete information about the current player at this time

int numEntities; // all of the entities that need to be presented

int firstEntity; // ab dieser Position sind im Ringbuffer die numEntities viele Entities des Snapshots

// ersetzt entities[Max_entities_in snapshot]

} snapshot_t;

typedef struct {

int lastServerCommandNum;

int currentServerCommandNum;

char serverCommands[MAX_SERVERCMDS][MAX_STRING_CHARS];

gameState_t gameState;

entityState_t baselines[MAX_GENTITIES];

entityState_t parseEntities[MAX_PARSE_ENTITIES];

int firstParseEntity;

snapshot_t snapshots[MAX_SNAPSHOTS];

snapshot_t *snap;

} demoState_t;

demoState_t ds;

==================

Parse_GameState

==================

static void Parse_GameState( sizebuf_t *msg ) {

int c;

int index;

char *configString;

memset( &ds, 0, sizeof( ds ) );

ds.lastServerCommandNum = MSG_ReadLong( msg );

ds.currentServerCommandNum = ds.lastServerCommandNum;

while( 1 ) {

c = MSG_ReadByte( msg );

if( c == -1 ) {

Com_Error( ERR_DROP, "Parse_GameState: read past end of demo message" );

}

if( c == SVC_EOM ) {

break;

}

switch( c ) {

default:

Com_Error( ERR_DROP, "Parse_GameState: bad command byte" );

break;

case SVC_CONFIGSTRING:

index = MSG_ReadShort( msg );

if( index < 0 || index >= MAX_CONFIGSTRINGS ) {

Com_Error( ERR_DROP, "Parse_GameState: configString index %i out of range", index );

}

configString = MSG_ReadBigString( msg );

Com_InsertIntoGameState( &ds.gameState, index, configString );

break;

case SVC_BASELINE:

index = MSG_ReadBits( msg, GENTITYNUM_BITS );

if( index < 0 || index >= MAX_GENTITIES ) {

Com_Error( ERR_DROP, "Parse_GameState: baseline index %i out of range", index );

}

MSG_ReadDeltaEntity( msg, NULL, &ds.baselines[index], index );

break;

}

// FIXME: unknown stuff, not used in demos?

MSG_ReadLong( msg );

demo.gameStatesParsed++;

}

=====================================================================

ACTION MESSAGES

=====================================================================

=====================

Parse_ServerCommand

=====================

static void Parse_ServerCommand( sizebuf_t *msg ) {

int number;

char *string;

number = MSG_ReadLong( msg );

string = MSG_ReadString( msg );

if( number < ds.lastServerCommandNum ) {

return; // we have already received this command

}

ds.lastServerCommandNum = number;

// archive the command to be processed later

Q_strncpyz( ds.serverCommands[number & SERVERCMD_MASK], string, sizeof( ds.serverCommands[0] ) );

}

==================

Parse_DeltaEntity

Parses deltas from the given base and adds the resulting entity

to the current frame

==================

static void Parse_DeltaEntity( sizebuf_t *msg, snapshot_t *frame, int newnum, entityState_t *old, qboolean unchanged ) {

entityState_t *state;

state = &ds.parseEntities[ds.firstParseEntity & PARSE_ENTITIES_MASK];

if( unchanged ) {

memcpy( state, old, sizeof( *state ) ); // don't read any bits

} else {

MSG_ReadDeltaEntity( msg, old, state, newnum );

if( state->number == ENTITYNUM_NONE ) {

// the entity present in oldframe is not in the current frame

return;

}

ds.firstParseEntity++;

frame->numEntities++;

}

==================

Parse_PacketEntities

An svc_packetentities has just been parsed, deal with the

rest of the data stream.

==================

static void Parse_PacketEntities( sizebuf_t *msg, snapshot_t *oldframe, snapshot_t *newframe ) {

int newnum;

entityState_t *oldstate;

int oldindex, oldnum;

newframe->firstEntity = ds.firstParseEntity;

newframe->numEntities = 0;

// delta from the entities present in oldframe

oldindex = 0;

if( !oldframe ) {

oldnum = 99999;

} else {

if( oldindex >= oldframe->numEntities ) {

oldnum = 99999;

} else {

oldstate = &ds.parseEntities[(oldframe->firstEntity + oldindex) & PARSE_ENTITIES_MASK];

oldnum = oldstate->number;

}

while( 1 ) {

newnum = MSG_ReadBits( msg, GENTITYNUM_BITS );

if( newnum < 0 || newnum >= MAX_GENTITIES ) {

Com_Error( ERR_DROP, "Parse_PacketEntities: bad number %i", newnum );

}

if( msg->readcount > msg->cursize ) {

Com_Error( ERR_DROP, "Parse_PacketEntities: end of message" );

}

if( newnum == ENTITYNUM_NONE ) {

break; // end of packetentities

}

while( oldnum < newnum ) {

// one or more entities from the old packet are unchanged

Parse_DeltaEntity( msg, newframe, oldnum, oldstate, qtrue );

oldindex++;

if( oldindex >= oldframe->numEntities ) {

oldnum = 99999;

} else {

oldstate = &ds.parseEntities[(oldframe->firstEntity + oldindex) & PARSE_ENTITIES_MASK];

oldnum = oldstate->number;

}

if( oldnum == newnum ) {

// delta from previous state

Parse_DeltaEntity( msg, newframe, newnum, oldstate, qfalse );

oldindex++;

if( oldindex >= oldframe->numEntities ) {

oldnum = 99999;

} else {

oldstate = &ds.parseEntities[(oldframe->firstEntity + oldindex) & PARSE_ENTITIES_MASK];

oldnum = oldstate->number;

}

continue;

}

if( oldnum > newnum ) {

// delta from baseline

Parse_DeltaEntity( msg, newframe, newnum, &ds.baselines[newnum], qfalse );

}

// any remaining entities in the old frame are copied over

while( oldnum != 99999 ) {

// one or more entities from the old packet are unchanged

Parse_DeltaEntity( msg, newframe, oldnum, oldstate, qtrue );

oldindex++;

if( oldindex >= oldframe->numEntities ) {

oldnum = 99999;

} else {

oldstate = &ds.parseEntities[(oldframe->firstEntity + oldindex) & PARSE_ENTITIES_MASK];

oldnum = oldstate->number;

}

=====================

ParseSnapshot

=====================

static void Parse_Snapshot( sizebuf_t *msg ) {

snapshot_t *oldsnap;

int delta;

int len;

// save the frame off in the backup array for later delta comparisons

ds.snap = &ds.snapshots[demo.demoMessageSequence & SNAPSHOT_MASK];

memset( ds.snap, 0, sizeof( *ds.snap ) );

ds.snap->seq = demo.demoMessageSequence;

ds.snap->serverTime = MSG_ReadLong( msg );

// If the frame is delta compressed from data that we

// no longer have available, we must suck up the rest of

// the frame, but not use it, then ask for a non-compressed

// message

delta = MSG_ReadByte( msg );

if( delta ) {

ds.snap->deltaSeq = demo.demoMessageSequence - delta;

oldsnap = &ds.snapshots[ds.snap->deltaSeq & SNAPSHOT_MASK];

if( !oldsnap->valid ) {

// should never happen

Com_Printf( "Delta from invalid frame (not supposed to happen!).\n" );

} else if( oldsnap->seq != ds.snap->deltaSeq ) {

// The frame that the server did the delta from

// is too old, so we can't reconstruct it properly.

Com_Printf( "Delta frame too old.\n" );

} else if( ds.firstParseEntity - oldsnap->firstEntity >

MAX_PARSE_ENTITIES - MAX_ENTITIES_IN_SNAPSHOT )

{

Com_Printf( "Delta parse_entities too old.\n" );

} else {

ds.snap->valid = qtrue; // valid delta parse

}

} else {

oldsnap = NULL;

ds.snap->deltaSeq = -1;

ds.snap->valid = qtrue; // uncompressed frame

}

// read snapFlags

ds.snap->snapFlags = MSG_ReadByte( msg );

// read areabits

len = MSG_ReadByte( msg );

MSG_ReadData( msg, ds.snap->areamask, len );

// read playerinfo

MSG_ReadDeltaPlayerstate( msg, oldsnap ? &oldsnap->ps : NULL, &ds.snap->ps );

// read packet entities

Parse_PacketEntities( msg, oldsnap, ds.snap );

}

=====================

Parse_DemoMessage

=====================

static void Parse_DemoMessage( sizebuf_t *msg ) {

int cmd;

// remaining data is Huffman compressed

MSG_SetBitstream( msg );

MSG_ReadLong( msg ); // FIXME: not used in demos

// parse the message

while( 1 ) {

if( msg->readcount > msg->cursize ) {

Com_Error( ERR_DROP, "Parse_DemoMessage: read past end of demo message" );

break;

}

cmd = MSG_ReadByte( msg );

if( cmd == SVC_EOM ) {

break;

}

// other commands

switch( cmd ) {

default:

case SVC_BASELINE:

case SVC_CONFIGSTRING:

case SVC_DOWNLOAD:

Com_Error( ERR_DROP, "Parse_DemoMessage: illegible demo message" );

break;

case SVC_NOP: /* do nothing */ break;

case SVC_GAMESTATE: Parse_GameState( msg ); break;

case SVC_SERVERCOMMAND: Parse_ServerCommand( msg ); break;

case SVC_SNAPSHOT: Parse_Snapshot( msg ); break;

}

11. Thanks to

- Martin Otten for Argus

- ID Software for releasing Quake II source code and Q3 SDK