1 /*
2 ===========================================================================
3 Copyright (C) 1999-2005 Id Software, Inc.
4
5 This file is part of Quake III Arena source code.
6
7 Quake III Arena source code is free software; you can redistribute it
8 and/or modify it under the terms of the GNU General Public License as
9 published by the Free Software Foundation; either version 2 of the License,
10 or (at your option) any later version.
11
12 Quake III Arena source code is distributed in the hope that it will be
13 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with Quake III Arena source code; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 ===========================================================================
21 */
22
23 #include "server.h"
24
25
26 /*
27 =============================================================================
28
29 Delta encode a client frame onto the network channel
30
31 A normal server packet will look like:
32
33 4 sequence number (high bit set if an oversize fragment)
34 <optional reliable commands>
35 1 svc_snapshot
36 4 last client reliable command
37 4 serverTime
38 1 lastframe for delta compression
39 1 snapFlags
40 1 areaBytes
41 <areabytes>
42 <playerstate>
43 <packetentities>
44
45 =============================================================================
46 */
47
48 /*
49 =============
50 SV_EmitPacketEntities
51
52 Writes a delta update of an entityState_t list to the message.
53 =============
54 */
SV_EmitPacketEntities(clientSnapshot_t * from,clientSnapshot_t * to,msg_t * msg)55 static void SV_EmitPacketEntities( clientSnapshot_t *from, clientSnapshot_t *to, msg_t *msg ) {
56 entityState_t *oldent, *newent;
57 int oldindex, newindex;
58 int oldnum, newnum;
59 int from_num_entities;
60
61 // generate the delta update
62 if ( !from ) {
63 from_num_entities = 0;
64 } else {
65 from_num_entities = from->num_entities;
66 }
67
68 newent = NULL;
69 oldent = NULL;
70 newindex = 0;
71 oldindex = 0;
72 while ( newindex < to->num_entities || oldindex < from_num_entities ) {
73 if ( newindex >= to->num_entities ) {
74 newnum = 9999;
75 } else {
76 newent = &svs.snapshotEntities[(to->first_entity+newindex) % svs.numSnapshotEntities];
77 newnum = newent->number;
78 }
79
80 if ( oldindex >= from_num_entities ) {
81 oldnum = 9999;
82 } else {
83 oldent = &svs.snapshotEntities[(from->first_entity+oldindex) % svs.numSnapshotEntities];
84 oldnum = oldent->number;
85 }
86
87 if ( newnum == oldnum ) {
88 // delta update from old position
89 // because the force parm is qfalse, this will not result
90 // in any bytes being emited if the entity has not changed at all
91 MSG_WriteDeltaEntity (msg, oldent, newent, qfalse );
92 oldindex++;
93 newindex++;
94 continue;
95 }
96
97 if ( newnum < oldnum ) {
98 // this is a new entity, send it from the baseline
99 MSG_WriteDeltaEntity (msg, &sv.svEntities[newnum].baseline, newent, qtrue );
100 newindex++;
101 continue;
102 }
103
104 if ( newnum > oldnum ) {
105 // the old entity isn't present in the new message
106 MSG_WriteDeltaEntity (msg, oldent, NULL, qtrue );
107 oldindex++;
108 continue;
109 }
110 }
111
112 MSG_WriteBits( msg, (MAX_GENTITIES-1), GENTITYNUM_BITS ); // end of packetentities
113 }
114
115
116
117 /*
118 ==================
119 SV_WriteSnapshotToClient
120 ==================
121 */
SV_WriteSnapshotToClient(client_t * client,msg_t * msg)122 static void SV_WriteSnapshotToClient( client_t *client, msg_t *msg ) {
123 clientSnapshot_t *frame, *oldframe;
124 int lastframe;
125 int i;
126 int snapFlags;
127
128 // this is the snapshot we are creating
129 frame = &client->frames[ client->netchan.outgoingSequence & PACKET_MASK ];
130
131 // try to use a previous frame as the source for delta compressing the snapshot
132 if ( client->deltaMessage <= 0 || client->state != CS_ACTIVE ) {
133 // client is asking for a retransmit
134 oldframe = NULL;
135 lastframe = 0;
136 } else if ( client->netchan.outgoingSequence - client->deltaMessage
137 >= (PACKET_BACKUP - 3) ) {
138 // client hasn't gotten a good message through in a long time
139 Com_DPrintf ("%s: Delta request from out of date packet.\n", client->name);
140 oldframe = NULL;
141 lastframe = 0;
142 } else {
143 // we have a valid snapshot to delta from
144 oldframe = &client->frames[ client->deltaMessage & PACKET_MASK ];
145 lastframe = client->netchan.outgoingSequence - client->deltaMessage;
146
147 // the snapshot's entities may still have rolled off the buffer, though
148 if ( oldframe->first_entity <= svs.nextSnapshotEntities - svs.numSnapshotEntities ) {
149 Com_DPrintf ("%s: Delta request from out of date entities.\n", client->name);
150 oldframe = NULL;
151 lastframe = 0;
152 }
153 }
154
155 MSG_WriteByte (msg, svc_snapshot);
156
157 // NOTE, MRE: now sent at the start of every message from server to client
158 // let the client know which reliable clientCommands we have received
159 //MSG_WriteLong( msg, client->lastClientCommand );
160
161 // send over the current server time so the client can drift
162 // its view of time to try to match
163 if( client->oldServerTime ) {
164 // The server has not yet got an acknowledgement of the
165 // new gamestate from this client, so continue to send it
166 // a time as if the server has not restarted. Note from
167 // the client's perspective this time is strictly speaking
168 // incorrect, but since it'll be busy loading a map at
169 // the time it doesn't really matter.
170 MSG_WriteLong (msg, sv.time + client->oldServerTime);
171 } else {
172 MSG_WriteLong (msg, sv.time);
173 }
174
175 // what we are delta'ing from
176 MSG_WriteByte (msg, lastframe);
177
178 snapFlags = svs.snapFlagServerBit;
179 if ( client->rateDelayed ) {
180 snapFlags |= SNAPFLAG_RATE_DELAYED;
181 }
182 if ( client->state != CS_ACTIVE ) {
183 snapFlags |= SNAPFLAG_NOT_ACTIVE;
184 }
185
186 MSG_WriteByte (msg, snapFlags);
187
188 // send over the areabits
189 MSG_WriteByte (msg, frame->areabytes);
190 MSG_WriteData (msg, frame->areabits, frame->areabytes);
191
192 // delta encode the playerstate
193 if ( oldframe ) {
194 MSG_WriteDeltaPlayerstate( msg, &oldframe->ps, &frame->ps );
195 } else {
196 MSG_WriteDeltaPlayerstate( msg, NULL, &frame->ps );
197 }
198
199 // delta encode the entities
200 SV_EmitPacketEntities (oldframe, frame, msg);
201
202 // padding for rate debugging
203 if ( sv_padPackets->integer ) {
204 for ( i = 0 ; i < sv_padPackets->integer ; i++ ) {
205 MSG_WriteByte (msg, svc_nop);
206 }
207 }
208 }
209
210
211 /*
212 ==================
213 SV_UpdateServerCommandsToClient
214
215 (re)send all server commands the client hasn't acknowledged yet
216 ==================
217 */
SV_UpdateServerCommandsToClient(client_t * client,msg_t * msg)218 void SV_UpdateServerCommandsToClient( client_t *client, msg_t *msg ) {
219 int i;
220
221 // write any unacknowledged serverCommands
222 for ( i = client->reliableAcknowledge + 1 ; i <= client->reliableSequence ; i++ ) {
223 MSG_WriteByte( msg, svc_serverCommand );
224 MSG_WriteLong( msg, i );
225 MSG_WriteString( msg, client->reliableCommands[ i & (MAX_RELIABLE_COMMANDS-1) ] );
226 }
227 client->reliableSent = client->reliableSequence;
228 }
229
230 /*
231 =============================================================================
232
233 Build a client snapshot structure
234
235 =============================================================================
236 */
237
238 #define MAX_SNAPSHOT_ENTITIES 1024
239 typedef struct {
240 int numSnapshotEntities;
241 int snapshotEntities[MAX_SNAPSHOT_ENTITIES];
242 } snapshotEntityNumbers_t;
243
244 /*
245 =======================
246 SV_QsortEntityNumbers
247 =======================
248 */
SV_QsortEntityNumbers(const void * a,const void * b)249 static int QDECL SV_QsortEntityNumbers( const void *a, const void *b ) {
250 int *ea, *eb;
251
252 ea = (int *)a;
253 eb = (int *)b;
254
255 if ( *ea == *eb ) {
256 Com_Error( ERR_DROP, "SV_QsortEntityStates: duplicated entity" );
257 }
258
259 if ( *ea < *eb ) {
260 return -1;
261 }
262
263 return 1;
264 }
265
266
267 /*
268 ===============
269 SV_AddEntToSnapshot
270 ===============
271 */
SV_AddEntToSnapshot(svEntity_t * svEnt,sharedEntity_t * gEnt,snapshotEntityNumbers_t * eNums)272 static void SV_AddEntToSnapshot( svEntity_t *svEnt, sharedEntity_t *gEnt, snapshotEntityNumbers_t *eNums ) {
273 // if we have already added this entity to this snapshot, don't add again
274 if ( svEnt->snapshotCounter == sv.snapshotCounter ) {
275 return;
276 }
277 svEnt->snapshotCounter = sv.snapshotCounter;
278
279 // if we are full, silently discard entities
280 if ( eNums->numSnapshotEntities == MAX_SNAPSHOT_ENTITIES ) {
281 return;
282 }
283
284 eNums->snapshotEntities[ eNums->numSnapshotEntities ] = gEnt->s.number;
285 eNums->numSnapshotEntities++;
286 }
287
288 /*
289 ===============
290 SV_AddEntitiesVisibleFromPoint
291 ===============
292 */
SV_AddEntitiesVisibleFromPoint(vec3_t origin,clientSnapshot_t * frame,snapshotEntityNumbers_t * eNums,qboolean portal)293 static void SV_AddEntitiesVisibleFromPoint( vec3_t origin, clientSnapshot_t *frame,
294 snapshotEntityNumbers_t *eNums, qboolean portal ) {
295 int e, i;
296 sharedEntity_t *ent;
297 svEntity_t *svEnt;
298 int l;
299 int clientarea, clientcluster;
300 int leafnum;
301 int c_fullsend;
302 byte *clientpvs;
303 byte *bitvector;
304
305 // during an error shutdown message we may need to transmit
306 // the shutdown message after the server has shutdown, so
307 // specfically check for it
308 if ( !sv.state ) {
309 return;
310 }
311
312 leafnum = CM_PointLeafnum (origin);
313 clientarea = CM_LeafArea (leafnum);
314 clientcluster = CM_LeafCluster (leafnum);
315
316 // calculate the visible areas
317 frame->areabytes = CM_WriteAreaBits( frame->areabits, clientarea );
318
319 clientpvs = CM_ClusterPVS (clientcluster);
320
321 c_fullsend = 0;
322
323 for ( e = 0 ; e < sv.num_entities ; e++ ) {
324 ent = SV_GentityNum(e);
325
326 // never send entities that aren't linked in
327 if ( !ent->r.linked ) {
328 continue;
329 }
330
331 if (ent->s.number != e) {
332 Com_DPrintf ("FIXING ENT->S.NUMBER!!!\n");
333 ent->s.number = e;
334 }
335
336 // entities can be flagged to explicitly not be sent to the client
337 if ( ent->r.svFlags & SVF_NOCLIENT ) {
338 continue;
339 }
340
341 // entities can be flagged to be sent to only one client
342 if ( ent->r.svFlags & SVF_SINGLECLIENT ) {
343 if ( ent->r.singleClient != frame->ps.clientNum ) {
344 continue;
345 }
346 }
347 // entities can be flagged to be sent to everyone but one client
348 if ( ent->r.svFlags & SVF_NOTSINGLECLIENT ) {
349 if ( ent->r.singleClient == frame->ps.clientNum ) {
350 continue;
351 }
352 }
353 // entities can be flagged to be sent to a given mask of clients
354 if ( ent->r.svFlags & SVF_CLIENTMASK ) {
355 if (frame->ps.clientNum >= 32)
356 Com_Error( ERR_DROP, "SVF_CLIENTMASK: cientNum > 32\n" );
357 if (~ent->r.singleClient & (1 << frame->ps.clientNum))
358 continue;
359 }
360
361 svEnt = SV_SvEntityForGentity( ent );
362
363 // don't double add an entity through portals
364 if ( svEnt->snapshotCounter == sv.snapshotCounter ) {
365 continue;
366 }
367
368 // broadcast entities are always sent
369 if ( ent->r.svFlags & SVF_BROADCAST ) {
370 SV_AddEntToSnapshot( svEnt, ent, eNums );
371 continue;
372 }
373
374 // ignore if not touching a PV leaf
375 // check area
376 if ( !CM_AreasConnected( clientarea, svEnt->areanum ) ) {
377 // doors can legally straddle two areas, so
378 // we may need to check another one
379 if ( !CM_AreasConnected( clientarea, svEnt->areanum2 ) ) {
380 continue; // blocked by a door
381 }
382 }
383
384 bitvector = clientpvs;
385
386 // check individual leafs
387 if ( !svEnt->numClusters ) {
388 continue;
389 }
390 l = 0;
391 for ( i=0 ; i < svEnt->numClusters ; i++ ) {
392 l = svEnt->clusternums[i];
393 if ( bitvector[l >> 3] & (1 << (l&7) ) ) {
394 break;
395 }
396 }
397
398 // if we haven't found it to be visible,
399 // check overflow clusters that coudln't be stored
400 if ( i == svEnt->numClusters ) {
401 if ( svEnt->lastCluster ) {
402 for ( ; l <= svEnt->lastCluster ; l++ ) {
403 if ( bitvector[l >> 3] & (1 << (l&7) ) ) {
404 break;
405 }
406 }
407 if ( l == svEnt->lastCluster ) {
408 continue; // not visible
409 }
410 } else {
411 continue;
412 }
413 }
414
415 // add it
416 SV_AddEntToSnapshot( svEnt, ent, eNums );
417
418 // if its a portal entity, add everything visible from its camera position
419 if ( ent->r.svFlags & SVF_PORTAL ) {
420 if ( ent->s.generic1 ) {
421 vec3_t dir;
422 VectorSubtract(ent->s.origin, origin, dir);
423 if ( VectorLengthSquared(dir) > (float) ent->s.generic1 * ent->s.generic1 ) {
424 continue;
425 }
426 }
427 SV_AddEntitiesVisibleFromPoint( ent->s.origin2, frame, eNums, qtrue );
428 }
429
430 }
431 }
432
433 /*
434 =============
435 SV_BuildClientSnapshot
436
437 Decides which entities are going to be visible to the client, and
438 copies off the playerstate and areabits.
439
440 This properly handles multiple recursive portals, but the render
441 currently doesn't.
442
443 For viewing through other player's eyes, clent can be something other than client->gentity
444 =============
445 */
SV_BuildClientSnapshot(client_t * client)446 static void SV_BuildClientSnapshot( client_t *client ) {
447 vec3_t org;
448 clientSnapshot_t *frame;
449 snapshotEntityNumbers_t entityNumbers;
450 int i;
451 sharedEntity_t *ent;
452 entityState_t *state;
453 svEntity_t *svEnt;
454 sharedEntity_t *clent;
455 int clientNum;
456 playerState_t *ps;
457
458 // bump the counter used to prevent double adding
459 sv.snapshotCounter++;
460
461 // this is the frame we are creating
462 frame = &client->frames[ client->netchan.outgoingSequence & PACKET_MASK ];
463
464 // clear everything in this snapshot
465 entityNumbers.numSnapshotEntities = 0;
466 Com_Memset( frame->areabits, 0, sizeof( frame->areabits ) );
467
468 // https://zerowing.idsoftware.com/bugzilla/show_bug.cgi?id=62
469 frame->num_entities = 0;
470
471 clent = client->gentity;
472 if ( !clent || client->state == CS_ZOMBIE ) {
473 return;
474 }
475
476 // grab the current playerState_t
477 ps = SV_GameClientNum( client - svs.clients );
478 frame->ps = *ps;
479
480 // never send client's own entity, because it can
481 // be regenerated from the playerstate
482 clientNum = frame->ps.clientNum;
483 if ( clientNum < 0 || clientNum >= MAX_GENTITIES ) {
484 Com_Error( ERR_DROP, "SV_SvEntityForGentity: bad gEnt" );
485 }
486 svEnt = &sv.svEntities[ clientNum ];
487
488 svEnt->snapshotCounter = sv.snapshotCounter;
489
490 // find the client's viewpoint
491 VectorCopy( ps->origin, org );
492 org[2] += ps->viewheight;
493
494 // add all the entities directly visible to the eye, which
495 // may include portal entities that merge other viewpoints
496 SV_AddEntitiesVisibleFromPoint( org, frame, &entityNumbers, qfalse );
497
498 // if there were portals visible, there may be out of order entities
499 // in the list which will need to be resorted for the delta compression
500 // to work correctly. This also catches the error condition
501 // of an entity being included twice.
502 qsort( entityNumbers.snapshotEntities, entityNumbers.numSnapshotEntities,
503 sizeof( entityNumbers.snapshotEntities[0] ), SV_QsortEntityNumbers );
504
505 // now that all viewpoint's areabits have been OR'd together, invert
506 // all of them to make it a mask vector, which is what the renderer wants
507 for ( i = 0 ; i < MAX_MAP_AREA_BYTES/4 ; i++ ) {
508 ((int *)frame->areabits)[i] = ((int *)frame->areabits)[i] ^ -1;
509 }
510
511 // copy the entity states out
512 frame->num_entities = 0;
513 frame->first_entity = svs.nextSnapshotEntities;
514 for ( i = 0 ; i < entityNumbers.numSnapshotEntities ; i++ ) {
515 ent = SV_GentityNum(entityNumbers.snapshotEntities[i]);
516 state = &svs.snapshotEntities[svs.nextSnapshotEntities % svs.numSnapshotEntities];
517 *state = ent->s;
518 svs.nextSnapshotEntities++;
519 // this should never hit, map should always be restarted first in SV_Frame
520 if ( svs.nextSnapshotEntities >= 0x7FFFFFFE ) {
521 Com_Error(ERR_FATAL, "svs.nextSnapshotEntities wrapped");
522 }
523 frame->num_entities++;
524 }
525 }
526
527
528 /*
529 ====================
530 SV_RateMsec
531
532 Return the number of msec a given size message is supposed
533 to take to clear, based on the current rate
534 ====================
535 */
536 #define HEADER_RATE_BYTES 48 // include our header, IP header, and some overhead
SV_RateMsec(client_t * client,int messageSize)537 static int SV_RateMsec( client_t *client, int messageSize ) {
538 int rate;
539 int rateMsec;
540
541 // individual messages will never be larger than fragment size
542 if ( messageSize > 1500 ) {
543 messageSize = 1500;
544 }
545 rate = client->rate;
546 if ( sv_maxRate->integer ) {
547 if ( sv_maxRate->integer < 1000 ) {
548 Cvar_Set( "sv_MaxRate", "1000" );
549 }
550 if ( sv_maxRate->integer < rate ) {
551 rate = sv_maxRate->integer;
552 }
553 }
554 if ( sv_minRate->integer ) {
555 if ( sv_minRate->integer < 1000 )
556 Cvar_Set( "sv_minRate", "1000" );
557 if ( sv_minRate->integer > rate )
558 rate = sv_minRate->integer;
559 }
560
561 rateMsec = ( messageSize + HEADER_RATE_BYTES ) * 1000 / rate * com_timescale->value;
562
563 return rateMsec;
564 }
565
566 /*
567 =======================
568 SV_SendMessageToClient
569
570 Called by SV_SendClientSnapshot and SV_SendClientGameState
571 =======================
572 */
SV_SendMessageToClient(msg_t * msg,client_t * client)573 void SV_SendMessageToClient( msg_t *msg, client_t *client ) {
574 int rateMsec;
575
576 // record information about the message
577 client->frames[client->netchan.outgoingSequence & PACKET_MASK].messageSize = msg->cursize;
578 client->frames[client->netchan.outgoingSequence & PACKET_MASK].messageSent = svs.time;
579 client->frames[client->netchan.outgoingSequence & PACKET_MASK].messageAcked = -1;
580
581 // send the datagram
582 SV_Netchan_Transmit( client, msg ); //msg->cursize, msg->data );
583
584 // set nextSnapshotTime based on rate and requested number of updates
585
586 // local clients get snapshots every server frame
587 // TTimo - https://zerowing.idsoftware.com/bugzilla/show_bug.cgi?id=491
588 // added sv_lanForceRate check
589 if ( client->netchan.remoteAddress.type == NA_LOOPBACK || (sv_lanForceRate->integer && Sys_IsLANAddress (client->netchan.remoteAddress)) ) {
590 client->nextSnapshotTime = svs.time + (1000.0 / sv_fps->integer * com_timescale->value);
591 return;
592 }
593
594 // normal rate / snapshotMsec calculation
595 rateMsec = SV_RateMsec(client, msg->cursize);
596
597 if ( rateMsec < client->snapshotMsec * com_timescale->value) {
598 // never send more packets than this, no matter what the rate is at
599 rateMsec = client->snapshotMsec * com_timescale->value;
600 client->rateDelayed = qfalse;
601 } else {
602 client->rateDelayed = qtrue;
603 }
604
605 client->nextSnapshotTime = svs.time + rateMsec * com_timescale->value;
606
607 // don't pile up empty snapshots while connecting
608 if ( client->state != CS_ACTIVE ) {
609 // a gigantic connection message may have already put the nextSnapshotTime
610 // more than a second away, so don't shorten it
611 // do shorten if client is downloading
612 if (!*client->downloadName && client->nextSnapshotTime < svs.time + 1000 * com_timescale->value)
613 client->nextSnapshotTime = svs.time + 1000 * com_timescale->value;
614 }
615 }
616
617
618 /*
619 =======================
620 SV_SendClientSnapshot
621
622 Also called by SV_FinalMessage
623
624 =======================
625 */
SV_SendClientSnapshot(client_t * client)626 void SV_SendClientSnapshot( client_t *client ) {
627 byte msg_buf[MAX_MSGLEN];
628 msg_t msg;
629
630 // build the snapshot
631 SV_BuildClientSnapshot( client );
632
633 // bots need to have their snapshots build, but
634 // the query them directly without needing to be sent
635 if ( client->gentity && client->gentity->r.svFlags & SVF_BOT ) {
636 return;
637 }
638
639 MSG_Init (&msg, msg_buf, sizeof(msg_buf));
640 msg.allowoverflow = qtrue;
641
642 // NOTE, MRE: all server->client messages now acknowledge
643 // let the client know which reliable clientCommands we have received
644 MSG_WriteLong( &msg, client->lastClientCommand );
645
646 // (re)send any reliable server commands
647 SV_UpdateServerCommandsToClient( client, &msg );
648
649 // send over all the relevant entityState_t
650 // and the playerState_t
651 SV_WriteSnapshotToClient( client, &msg );
652
653 // Add any download data if the client is downloading
654 SV_WriteDownloadToClient( client, &msg );
655
656 #if USE_VOIP
657 SV_WriteVoipToClient( client, &msg );
658 #endif
659
660 // check for overflow
661 if ( msg.overflowed ) {
662 Com_Printf ("WARNING: msg overflowed for %s\n", client->name);
663 MSG_Clear (&msg);
664 }
665
666 SV_SendMessageToClient( &msg, client );
667 }
668
669
670 /*
671 =======================
672 SV_SendClientMessages
673 =======================
674 */
SV_SendClientMessages(void)675 void SV_SendClientMessages( void ) {
676 int i;
677 client_t *c;
678
679 // send a message to each connected client
680 for (i=0, c = svs.clients ; i < sv_maxclients->integer ; i++, c++) {
681 if (!c->state) {
682 continue; // not connected
683 }
684
685 if ( svs.time < c->nextSnapshotTime ) {
686 continue; // not time yet
687 }
688
689 // send additional message fragments if the last message
690 // was too large to send at once
691 if ( c->netchan.unsentFragments ) {
692 c->nextSnapshotTime = svs.time +
693 SV_RateMsec( c, c->netchan.unsentLength - c->netchan.unsentFragmentStart );
694 SV_Netchan_TransmitNextFragment( c );
695 continue;
696 }
697
698 // generate and send a new message
699 SV_SendClientSnapshot( c );
700 }
701 }
702
703