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