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