1 /*
2 ===========================================================================
3
4 Return to Castle Wolfenstein multiplayer GPL Source Code
5 Copyright (C) 1999-2010 id Software LLC, a ZeniMax Media company.
6
7 This file is part of the Return to Castle Wolfenstein multiplayer GPL Source Code (“RTCW MP Source Code”).
8
9 RTCW MP Source Code is free software: you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation, either version 3 of the License, or
12 (at your option) any later version.
13
14 RTCW MP Source Code is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with RTCW MP Source Code. If not, see <http://www.gnu.org/licenses/>.
21
22 In addition, the RTCW MP Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the RTCW MP Source Code. If not, please request a copy in writing from id Software at the address below.
23
24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
25
26 ===========================================================================
27 */
28
29
30 /* This is based on the Adaptive Huffman algorithm described in Sayood's Data
31 * Compression book. The ranks are not actually stored, but implicitly defined
32 * by the location of a node within a doubly-linked list */
33
34 #include "q_shared.h"
35 #include "qcommon.h"
36
37 static int bloc = 0;
38
Huff_putBit(int bit,byte * fout,int * offset)39 void Huff_putBit( int bit, byte *fout, int *offset ) {
40 bloc = *offset;
41 if ( ( bloc & 7 ) == 0 ) {
42 fout[( bloc >> 3 )] = 0;
43 }
44 fout[( bloc >> 3 )] |= bit << ( bloc & 7 );
45 bloc++;
46 *offset = bloc;
47 }
48
Huff_getBloc(void)49 int Huff_getBloc( void ) {
50 return bloc;
51 }
52
Huff_setBloc(int _bloc)53 void Huff_setBloc( int _bloc ) {
54 bloc = _bloc;
55 }
56
Huff_getBit(byte * fin,int * offset)57 int Huff_getBit( byte *fin, int *offset ) {
58 int t;
59 bloc = *offset;
60 t = ( fin[( bloc >> 3 )] >> ( bloc & 7 ) ) & 0x1;
61 bloc++;
62 *offset = bloc;
63 return t;
64 }
65
66 /* Add a bit to the output file (buffered) */
add_bit(char bit,byte * fout)67 static void add_bit( char bit, byte *fout ) {
68 if ( ( bloc & 7 ) == 0 ) {
69 fout[( bloc >> 3 )] = 0;
70 }
71 fout[( bloc >> 3 )] |= bit << ( bloc & 7 );
72 bloc++;
73 }
74
75 /* Receive one bit from the input file (buffered) */
get_bit(byte * fin)76 static int get_bit( byte *fin ) {
77 int t;
78 t = ( fin[( bloc >> 3 )] >> ( bloc & 7 ) ) & 0x1;
79 bloc++;
80 return t;
81 }
82
get_ppnode(huff_t * huff)83 static node_t **get_ppnode( huff_t* huff ) {
84 node_t **tppnode;
85 if ( !huff->freelist ) {
86 return &( huff->nodePtrs[huff->blocPtrs++] );
87 } else {
88 tppnode = huff->freelist;
89 huff->freelist = (node_t **)*tppnode;
90 return tppnode;
91 }
92 }
93
free_ppnode(huff_t * huff,node_t ** ppnode)94 static void free_ppnode( huff_t* huff, node_t **ppnode ) {
95 *ppnode = (node_t *)huff->freelist;
96 huff->freelist = ppnode;
97 }
98
99 /* Swap the location of these two nodes in the tree */
swap(huff_t * huff,node_t * node1,node_t * node2)100 static void swap( huff_t* huff, node_t *node1, node_t *node2 ) {
101 node_t *par1, *par2;
102
103 par1 = node1->parent;
104 par2 = node2->parent;
105
106 if ( par1 ) {
107 if ( par1->left == node1 ) {
108 par1->left = node2;
109 } else {
110 par1->right = node2;
111 }
112 } else {
113 huff->tree = node2;
114 }
115
116 if ( par2 ) {
117 if ( par2->left == node2 ) {
118 par2->left = node1;
119 } else {
120 par2->right = node1;
121 }
122 } else {
123 huff->tree = node1;
124 }
125
126 node1->parent = par2;
127 node2->parent = par1;
128 }
129
130 /* Swap these two nodes in the linked list (update ranks) */
swaplist(node_t * node1,node_t * node2)131 static void swaplist( node_t *node1, node_t *node2 ) {
132 node_t *par1;
133
134 par1 = node1->next;
135 node1->next = node2->next;
136 node2->next = par1;
137
138 par1 = node1->prev;
139 node1->prev = node2->prev;
140 node2->prev = par1;
141
142 if ( node1->next == node1 ) {
143 node1->next = node2;
144 }
145 if ( node2->next == node2 ) {
146 node2->next = node1;
147 }
148 if ( node1->next ) {
149 node1->next->prev = node1;
150 }
151 if ( node2->next ) {
152 node2->next->prev = node2;
153 }
154 if ( node1->prev ) {
155 node1->prev->next = node1;
156 }
157 if ( node2->prev ) {
158 node2->prev->next = node2;
159 }
160 }
161
162 /* Do the increments */
increment(huff_t * huff,node_t * node)163 static void increment( huff_t* huff, node_t *node ) {
164 node_t *lnode;
165
166 if ( !node ) {
167 return;
168 }
169
170 if ( node->next != NULL && node->next->weight == node->weight ) {
171 lnode = *node->head;
172 if ( lnode != node->parent ) {
173 swap( huff, lnode, node );
174 }
175 swaplist( lnode, node );
176 }
177 if ( node->prev && node->prev->weight == node->weight ) {
178 *node->head = node->prev;
179 } else {
180 *node->head = NULL;
181 free_ppnode( huff, node->head );
182 }
183 node->weight++;
184 if ( node->next && node->next->weight == node->weight ) {
185 node->head = node->next->head;
186 } else {
187 node->head = get_ppnode( huff );
188 *node->head = node;
189 }
190 if ( node->parent ) {
191 increment( huff, node->parent );
192 if ( node->prev == node->parent ) {
193 swaplist( node, node->parent );
194 if ( *node->head == node ) {
195 *node->head = node->parent;
196 }
197 }
198 }
199 }
200
Huff_addRef(huff_t * huff,byte ch)201 void Huff_addRef( huff_t* huff, byte ch ) {
202 node_t *tnode, *tnode2;
203 if ( huff->loc[ch] == NULL ) { /* if this is the first transmission of this node */
204 tnode = &( huff->nodeList[huff->blocNode++] );
205 tnode2 = &( huff->nodeList[huff->blocNode++] );
206
207 tnode2->symbol = INTERNAL_NODE;
208 tnode2->weight = 1;
209 tnode2->next = huff->lhead->next;
210 if ( huff->lhead->next ) {
211 huff->lhead->next->prev = tnode2;
212 if ( huff->lhead->next->weight == 1 ) {
213 tnode2->head = huff->lhead->next->head;
214 } else {
215 tnode2->head = get_ppnode( huff );
216 *tnode2->head = tnode2;
217 }
218 } else {
219 tnode2->head = get_ppnode( huff );
220 *tnode2->head = tnode2;
221 }
222 huff->lhead->next = tnode2;
223 tnode2->prev = huff->lhead;
224
225 tnode->symbol = ch;
226 tnode->weight = 1;
227 tnode->next = huff->lhead->next;
228 if ( huff->lhead->next ) {
229 huff->lhead->next->prev = tnode;
230 if ( huff->lhead->next->weight == 1 ) {
231 tnode->head = huff->lhead->next->head;
232 } else {
233 /* this should never happen */
234 tnode->head = get_ppnode( huff );
235 *tnode->head = tnode2;
236 }
237 } else {
238 /* this should never happen */
239 tnode->head = get_ppnode( huff );
240 *tnode->head = tnode;
241 }
242 huff->lhead->next = tnode;
243 tnode->prev = huff->lhead;
244 tnode->left = tnode->right = NULL;
245
246 if ( huff->lhead->parent ) {
247 if ( huff->lhead->parent->left == huff->lhead ) { /* lhead is guaranteed to by the NYT */
248 huff->lhead->parent->left = tnode2;
249 } else {
250 huff->lhead->parent->right = tnode2;
251 }
252 } else {
253 huff->tree = tnode2;
254 }
255
256 tnode2->right = tnode;
257 tnode2->left = huff->lhead;
258
259 tnode2->parent = huff->lhead->parent;
260 huff->lhead->parent = tnode->parent = tnode2;
261
262 huff->loc[ch] = tnode;
263
264 increment( huff, tnode2->parent );
265 } else {
266 increment( huff, huff->loc[ch] );
267 }
268 }
269
270 /* Get a symbol */
Huff_Receive(node_t * node,int * ch,byte * fin)271 int Huff_Receive( node_t *node, int *ch, byte *fin ) {
272 while ( node && node->symbol == INTERNAL_NODE ) {
273 if ( get_bit( fin ) ) {
274 node = node->right;
275 } else {
276 node = node->left;
277 }
278 }
279 if ( !node ) {
280 return 0;
281 // Com_Error(ERR_DROP, "Illegal tree!");
282 }
283 return ( *ch = node->symbol );
284 }
285
286 /* Get a symbol */
Huff_offsetReceive(node_t * node,int * ch,byte * fin,int * offset,int maxoffset)287 void Huff_offsetReceive( node_t *node, int *ch, byte *fin, int *offset, int maxoffset ) {
288 bloc = *offset;
289 while ( node && node->symbol == INTERNAL_NODE ) {
290 if ( bloc >= maxoffset ) {
291 *ch = 0;
292 *offset = maxoffset + 1;
293 return;
294 }
295 if ( get_bit( fin ) ) {
296 node = node->right;
297 } else {
298 node = node->left;
299 }
300 }
301 if ( !node ) {
302 *ch = 0;
303 return;
304 // Com_Error(ERR_DROP, "Illegal tree!");
305 }
306 *ch = node->symbol;
307 *offset = bloc;
308 }
309
310 /* Send the prefix code for this node */
send(node_t * node,node_t * child,byte * fout,int maxoffset)311 static void send( node_t *node, node_t *child, byte *fout, int maxoffset ) {
312 if ( node->parent ) {
313 send( node->parent, node, fout, maxoffset );
314 }
315 if ( child ) {
316 if ( bloc >= maxoffset ) {
317 bloc = maxoffset + 1;
318 return;
319 }
320 if ( node->right == child ) {
321 add_bit( 1, fout );
322 } else {
323 add_bit( 0, fout );
324 }
325 }
326 }
327
328 /* Send a symbol */
Huff_transmit(huff_t * huff,int ch,byte * fout,int maxoffset)329 void Huff_transmit( huff_t *huff, int ch, byte *fout, int maxoffset ) {
330 int i;
331 if ( huff->loc[ch] == NULL ) {
332 /* node_t hasn't been transmitted, send a NYT, then the symbol */
333 Huff_transmit( huff, NYT, fout, maxoffset );
334 for ( i = 7; i >= 0; i-- ) {
335 add_bit( (char)( ( ch >> i ) & 0x1 ), fout );
336 }
337 } else {
338 send( huff->loc[ch], NULL, fout, maxoffset );
339 }
340 }
341
Huff_offsetTransmit(huff_t * huff,int ch,byte * fout,int * offset,int maxoffset)342 void Huff_offsetTransmit( huff_t *huff, int ch, byte *fout, int *offset, int maxoffset ) {
343 bloc = *offset;
344 send( huff->loc[ch], NULL, fout, maxoffset );
345 *offset = bloc;
346 }
347
Huff_Decompress(msg_t * mbuf,int offset)348 void Huff_Decompress( msg_t *mbuf, int offset ) {
349 int ch, cch, i, j, size;
350 byte seq[65536];
351 byte* buffer;
352 huff_t huff;
353
354 size = mbuf->cursize - offset;
355 buffer = mbuf->data + offset;
356
357 if ( size <= 0 ) {
358 return;
359 }
360
361 Com_Memset( &huff, 0, sizeof( huff_t ) );
362 // Initialize the tree & list with the NYT node
363 huff.tree = huff.lhead = huff.ltail = huff.loc[NYT] = &( huff.nodeList[huff.blocNode++] );
364 huff.tree->symbol = NYT;
365 huff.tree->weight = 0;
366 huff.lhead->next = huff.lhead->prev = NULL;
367 huff.tree->parent = huff.tree->left = huff.tree->right = NULL;
368
369 cch = buffer[0] * 256 + buffer[1];
370 // don't overflow with bad messages
371 if ( cch > mbuf->maxsize - offset ) {
372 cch = mbuf->maxsize - offset;
373 }
374 bloc = 16;
375
376 for ( j = 0; j < cch; j++ ) {
377 ch = 0;
378 // don't overflow reading from the messages
379 // FIXME: would it be better to have an overflow check in get_bit ?
380 if ( ( bloc >> 3 ) > size ) {
381 seq[j] = 0;
382 break;
383 }
384 Huff_Receive( huff.tree, &ch, buffer ); /* Get a character */
385 if ( ch == NYT ) { /* We got a NYT, get the symbol associated with it */
386 ch = 0;
387 for ( i = 0; i < 8; i++ ) {
388 ch = ( ch << 1 ) + get_bit( buffer );
389 }
390 }
391
392 seq[j] = ch; /* Write symbol */
393
394 Huff_addRef( &huff, (byte)ch ); /* Increment node */
395 }
396 mbuf->cursize = cch + offset;
397 Com_Memcpy( mbuf->data + offset, seq, cch );
398 }
399
400 extern int oldsize;
401
Huff_Compress(msg_t * mbuf,int offset)402 void Huff_Compress( msg_t *mbuf, int offset ) {
403 int i, ch, size;
404 byte seq[65536];
405 byte* buffer;
406 huff_t huff;
407
408 size = mbuf->cursize - offset;
409 buffer = mbuf->data + offset;
410
411 if ( size <= 0 ) {
412 return;
413 }
414
415 Com_Memset( &huff, 0, sizeof( huff_t ) );
416 // Add the NYT (not yet transmitted) node into the tree/list */
417 huff.tree = huff.lhead = huff.loc[NYT] = &( huff.nodeList[huff.blocNode++] );
418 huff.tree->symbol = NYT;
419 huff.tree->weight = 0;
420 huff.lhead->next = huff.lhead->prev = NULL;
421 huff.tree->parent = huff.tree->left = huff.tree->right = NULL;
422
423 seq[0] = ( size >> 8 );
424 seq[1] = size & 0xff;
425
426 bloc = 16;
427
428 for ( i = 0; i < size; i++ ) {
429 ch = buffer[i];
430 Huff_transmit( &huff, ch, seq, size << 3 ); /* Transmit symbol */
431 Huff_addRef( &huff, (byte)ch ); /* Do update */
432 }
433
434 bloc += 8; // next byte
435
436 mbuf->cursize = ( bloc >> 3 ) + offset;
437 Com_Memcpy( mbuf->data + offset, seq, ( bloc >> 3 ) );
438 }
439
Huff_Init(huffman_t * huff)440 void Huff_Init( huffman_t *huff ) {
441
442 Com_Memset( &huff->compressor, 0, sizeof( huff_t ) );
443 Com_Memset( &huff->decompressor, 0, sizeof( huff_t ) );
444
445 // Initialize the tree & list with the NYT node
446 huff->decompressor.tree = huff->decompressor.lhead = huff->decompressor.ltail = huff->decompressor.loc[NYT] = &( huff->decompressor.nodeList[huff->decompressor.blocNode++] );
447 huff->decompressor.tree->symbol = NYT;
448 huff->decompressor.tree->weight = 0;
449 huff->decompressor.lhead->next = huff->decompressor.lhead->prev = NULL;
450 huff->decompressor.tree->parent = huff->decompressor.tree->left = huff->decompressor.tree->right = NULL;
451
452 // Add the NYT (not yet transmitted) node into the tree/list */
453 huff->compressor.tree = huff->compressor.lhead = huff->compressor.loc[NYT] = &( huff->compressor.nodeList[huff->compressor.blocNode++] );
454 huff->compressor.tree->symbol = NYT;
455 huff->compressor.tree->weight = 0;
456 huff->compressor.lhead->next = huff->compressor.lhead->prev = NULL;
457 huff->compressor.tree->parent = huff->compressor.tree->left = huff->compressor.tree->right = NULL;
458 }
459
460