huffman.c (10889B)
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 Foobar; 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 "../game/q_shared.h" 28 #include "qcommon.h" 29 30 static int bloc = 0; 31 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 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) */ 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) */ 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 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 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 */ 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) */ 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 */ 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 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 */ 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 */ 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 */ 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 */ 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 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 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 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 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