/* =========================================================================== Copyright (C) 1999-2005 Id Software, Inc. This file is part of Quake III Arena source code. Quake III Arena source code is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. Quake III Arena source code is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with Quake III Arena source code; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA =========================================================================== */ /* This is based on the Adaptive Huffman algorithm described in Sayood's Data * Compression book. The ranks are not actually stored, but implicitly defined * by the location of a node within a doubly-linked list */ #include "q_shared.h" #include "qcommon.h" static int bloc = 0; void Huff_putBit( int bit, byte *fout, int *offset) { bloc = *offset; if ((bloc&7) == 0) { fout[(bloc>>3)] = 0; } fout[(bloc>>3)] |= bit << (bloc&7); bloc++; *offset = bloc; } int Huff_getBit( byte *fin, int *offset) { int t; bloc = *offset; t = (fin[(bloc>>3)] >> (bloc&7)) & 0x1; bloc++; *offset = bloc; return t; } /* Add a bit to the output file (buffered) */ static void add_bit (char bit, byte *fout) { if ((bloc&7) == 0) { fout[(bloc>>3)] = 0; } fout[(bloc>>3)] |= bit << (bloc&7); bloc++; } /* Receive one bit from the input file (buffered) */ static int get_bit (byte *fin) { int t; t = (fin[(bloc>>3)] >> (bloc&7)) & 0x1; bloc++; return t; } static node_t **get_ppnode(huff_t* huff) { node_t **tppnode; if (!huff->freelist) { return &(huff->nodePtrs[huff->blocPtrs++]); } else { tppnode = huff->freelist; huff->freelist = (node_t **)*tppnode; return tppnode; } } static void free_ppnode(huff_t* huff, node_t **ppnode) { *ppnode = (node_t *)huff->freelist; huff->freelist = ppnode; } /* Swap the location of these two nodes in the tree */ static void swap (huff_t* huff, node_t *node1, node_t *node2) { node_t *par1, *par2; par1 = node1->parent; par2 = node2->parent; if (par1) { if (par1->left == node1) { par1->left = node2; } else { par1->right = node2; } } else { huff->tree = node2; } if (par2) { if (par2->left == node2) { par2->left = node1; } else { par2->right = node1; } } else { huff->tree = node1; } node1->parent = par2; node2->parent = par1; } /* Swap these two nodes in the linked list (update ranks) */ static void swaplist(node_t *node1, node_t *node2) { node_t *par1; par1 = node1->next; node1->next = node2->next; node2->next = par1; par1 = node1->prev; node1->prev = node2->prev; node2->prev = par1; if (node1->next == node1) { node1->next = node2; } if (node2->next == node2) { node2->next = node1; } if (node1->next) { node1->next->prev = node1; } if (node2->next) { node2->next->prev = node2; } if (node1->prev) { node1->prev->next = node1; } if (node2->prev) { node2->prev->next = node2; } } /* Do the increments */ static void increment(huff_t* huff, node_t *node) { node_t *lnode; if (!node) { return; } if (node->next != NULL && node->next->weight == node->weight) { lnode = *node->head; if (lnode != node->parent) { swap(huff, lnode, node); } swaplist(lnode, node); } if (node->prev && node->prev->weight == node->weight) { *node->head = node->prev; } else { *node->head = NULL; free_ppnode(huff, node->head); } node->weight++; if (node->next && node->next->weight == node->weight) { node->head = node->next->head; } else { node->head = get_ppnode(huff); *node->head = node; } if (node->parent) { increment(huff, node->parent); if (node->prev == node->parent) { swaplist(node, node->parent); if (*node->head == node) { *node->head = node->parent; } } } } void Huff_addRef(huff_t* huff, byte ch) { node_t *tnode, *tnode2; if (huff->loc[ch] == NULL) { /* if this is the first transmission of this node */ tnode = &(huff->nodeList[huff->blocNode++]); tnode2 = &(huff->nodeList[huff->blocNode++]); tnode2->symbol = INTERNAL_NODE; tnode2->weight = 1; tnode2->next = huff->lhead->next; if (huff->lhead->next) { huff->lhead->next->prev = tnode2; if (huff->lhead->next->weight == 1) { tnode2->head = huff->lhead->next->head; } else { tnode2->head = get_ppnode(huff); *tnode2->head = tnode2; } } else { tnode2->head = get_ppnode(huff); *tnode2->head = tnode2; } huff->lhead->next = tnode2; tnode2->prev = huff->lhead; tnode->symbol = ch; tnode->weight = 1; tnode->next = huff->lhead->next; if (huff->lhead->next) { huff->lhead->next->prev = tnode; if (huff->lhead->next->weight == 1) { tnode->head = huff->lhead->next->head; } else { /* this should never happen */ tnode->head = get_ppnode(huff); *tnode->head = tnode2; } } else { /* this should never happen */ tnode->head = get_ppnode(huff); *tnode->head = tnode; } huff->lhead->next = tnode; tnode->prev = huff->lhead; tnode->left = tnode->right = NULL; if (huff->lhead->parent) { if (huff->lhead->parent->left == huff->lhead) { /* lhead is guaranteed to by the NYT */ huff->lhead->parent->left = tnode2; } else { huff->lhead->parent->right = tnode2; } } else { huff->tree = tnode2; } tnode2->right = tnode; tnode2->left = huff->lhead; tnode2->parent = huff->lhead->parent; huff->lhead->parent = tnode->parent = tnode2; huff->loc[ch] = tnode; increment(huff, tnode2->parent); } else { increment(huff, huff->loc[ch]); } } /* Get a symbol */ int Huff_Receive (node_t *node, int *ch, byte *fin) { while (node && node->symbol == INTERNAL_NODE) { if (get_bit(fin)) { node = node->right; } else { node = node->left; } } if (!node) { return 0; // Com_Error(ERR_DROP, "Illegal tree!\n"); } return (*ch = node->symbol); } /* Get a symbol */ void Huff_offsetReceive (node_t *node, int *ch, byte *fin, int *offset) { bloc = *offset; while (node && node->symbol == INTERNAL_NODE) { if (get_bit(fin)) { node = node->right; } else { node = node->left; } } if (!node) { *ch = 0; return; // Com_Error(ERR_DROP, "Illegal tree!\n"); } *ch = node->symbol; *offset = bloc; } /* Send the prefix code for this node */ static void send(node_t *node, node_t *child, byte *fout) { if (node->parent) { send(node->parent, node, fout); } if (child) { if (node->right == child) { add_bit(1, fout); } else { add_bit(0, fout); } } } /* Send a symbol */ void Huff_transmit (huff_t *huff, int ch, byte *fout) { int i; if (huff->loc[ch] == NULL) { /* node_t hasn't been transmitted, send a NYT, then the symbol */ Huff_transmit(huff, NYT, fout); for (i = 7; i >= 0; i--) { add_bit((char)((ch >> i) & 0x1), fout); } } else { send(huff->loc[ch], NULL, fout); } } void Huff_offsetTransmit (huff_t *huff, int ch, byte *fout, int *offset) { bloc = *offset; send(huff->loc[ch], NULL, fout); *offset = bloc; } void Huff_Decompress(msg_t *mbuf, int offset) { int ch, cch, i, j, size; byte seq[65536]; byte* buffer; huff_t huff; size = mbuf->cursize - offset; buffer = mbuf->data + offset; if ( size <= 0 ) { return; } Com_Memset(&huff, 0, sizeof(huff_t)); // Initialize the tree & list with the NYT node huff.tree = huff.lhead = huff.ltail = huff.loc[NYT] = &(huff.nodeList[huff.blocNode++]); huff.tree->symbol = NYT; huff.tree->weight = 0; huff.lhead->next = huff.lhead->prev = NULL; huff.tree->parent = huff.tree->left = huff.tree->right = NULL; cch = buffer[0]*256 + buffer[1]; // don't overflow with bad messages if ( cch > mbuf->maxsize - offset ) { cch = mbuf->maxsize - offset; } bloc = 16; for ( j = 0; j < cch; j++ ) { ch = 0; // don't overflow reading from the messages // FIXME: would it be better to have a overflow check in get_bit ? if ( (bloc >> 3) > size ) { seq[j] = 0; break; } Huff_Receive(huff.tree, &ch, buffer); /* Get a character */ if ( ch == NYT ) { /* We got a NYT, get the symbol associated with it */ ch = 0; for ( i = 0; i < 8; i++ ) { ch = (ch<<1) + get_bit(buffer); } } seq[j] = ch; /* Write symbol */ Huff_addRef(&huff, (byte)ch); /* Increment node */ } mbuf->cursize = cch + offset; Com_Memcpy(mbuf->data + offset, seq, cch); } extern int oldsize; void Huff_Compress(msg_t *mbuf, int offset) { int i, ch, size; byte seq[65536]; byte* buffer; huff_t huff; size = mbuf->cursize - offset; buffer = mbuf->data+ + offset; if (size<=0) { return; } Com_Memset(&huff, 0, sizeof(huff_t)); // Add the NYT (not yet transmitted) node into the tree/list */ huff.tree = huff.lhead = huff.loc[NYT] = &(huff.nodeList[huff.blocNode++]); huff.tree->symbol = NYT; huff.tree->weight = 0; huff.lhead->next = huff.lhead->prev = NULL; huff.tree->parent = huff.tree->left = huff.tree->right = NULL; huff.loc[NYT] = huff.tree; seq[0] = (size>>8); seq[1] = size&0xff; bloc = 16; for (i=0; i<size; i++ ) { ch = buffer[i]; Huff_transmit(&huff, ch, seq); /* Transmit symbol */ Huff_addRef(&huff, (byte)ch); /* Do update */ } bloc += 8; // next byte mbuf->cursize = (bloc>>3) + offset; Com_Memcpy(mbuf->data+offset, seq, (bloc>>3)); } void Huff_Init(huffman_t *huff) { Com_Memset(&huff->compressor, 0, sizeof(huff_t)); Com_Memset(&huff->decompressor, 0, sizeof(huff_t)); // Initialize the tree & list with the NYT node huff->decompressor.tree = huff->decompressor.lhead = huff->decompressor.ltail = huff->decompressor.loc[NYT] = &(huff->decompressor.nodeList[huff->decompressor.blocNode++]); huff->decompressor.tree->symbol = NYT; huff->decompressor.tree->weight = 0; huff->decompressor.lhead->next = huff->decompressor.lhead->prev = NULL; huff->decompressor.tree->parent = huff->decompressor.tree->left = huff->decompressor.tree->right = NULL; // Add the NYT (not yet transmitted) node into the tree/list */ huff->compressor.tree = huff->compressor.lhead = huff->compressor.loc[NYT] = &(huff->compressor.nodeList[huff->compressor.blocNode++]); huff->compressor.tree->symbol = NYT; huff->compressor.tree->weight = 0; huff->compressor.lhead->next = huff->compressor.lhead->prev = NULL; huff->compressor.tree->parent = huff->compressor.tree->left = huff->compressor.tree->right = NULL; huff->compressor.loc[NYT] = huff->compressor.tree; }