Main Page | Class Hierarchy | Alphabetical List | Data Structures | Directories | File List | Data Fields | Globals
code / qcommon

huffman.c File Reference

#include "../game/q_shared.h"
#include "qcommon.h"

Include dependency graph for huffman.c:

Include dependency graph

Go to the source code of this file.

Functions

void add_bit (char bit, byte *fout)
void free_ppnode (huff_t *huff, node_t **ppnode)
int get_bit (byte *fin)
node_t ** get_ppnode (huff_t *huff)
void Huff_addRef (huff_t *huff, byte ch)
void Huff_Compress (msg_t *mbuf, int offset)
void Huff_Decompress (msg_t *mbuf, int offset)
int Huff_getBit (byte *fin, int *offset)
void Huff_Init (huffman_t *huff)
void Huff_offsetReceive (node_t *node, int *ch, byte *fin, int *offset)
void Huff_offsetTransmit (huff_t *huff, int ch, byte *fout, int *offset)
void Huff_putBit (int bit, byte *fout, int *offset)
int Huff_Receive (node_t *node, int *ch, byte *fin)
void Huff_transmit (huff_t *huff, int ch, byte *fout)
void increment (huff_t *huff, node_t *node)
void send (node_t *node, node_t *child, byte *fout)
void swap (huff_t *huff, node_t *node1, node_t *node2)
void swaplist (node_t *node1, node_t *node2)

Variables

int bloc = 0
int oldsize

Function Documentation

void add_bit (  char  bit,
byte *  fout
)  [static]
 

Definition at line 52 of file huffman.c.

References bloc, and byte.

Referenced by Huff_transmit(), and send().

00052                                            {
00053     if ((bloc&7) == 0) {
00054         fout[(bloc>>3)] = 0;
00055     }
00056     fout[(bloc>>3)] |= bit << (bloc&7);
00057     bloc++;
00058 }

void free_ppnode (  huff_t *  huff,
node_t **  ppnode
)  [static]
 

Definition at line 79 of file huffman.c.

References huff_t::freelist, and node_t.

Referenced by increment().

00079                                                        {
00080     *ppnode = (node_t *)huff->freelist;
00081     huff->freelist = ppnode;
00082 }

int get_bit (  byte *  fin  )  [static]
 

Definition at line 61 of file huffman.c.

References bloc, byte, and t.

Referenced by Huff_Decompress(), Huff_offsetReceive(), and Huff_Receive().

00061                                {
00062     int t;
00063     t = (fin[(bloc>>3)] >> (bloc&7)) & 0x1;
00064     bloc++;
00065     return t;
00066 }

node_t** get_ppnode (  huff_t *  huff  )  [static]
 

Definition at line 68 of file huffman.c.

References huff_t::blocPtrs, huff_t::freelist, node_t, and huff_t::nodePtrs.

Referenced by Huff_addRef(), and increment().

00068                                          {
00069     node_t **tppnode;
00070     if (!huff->freelist) {
00071         return &(huff->nodePtrs[huff->blocPtrs++]);
00072     } else {
00073         tppnode = huff->freelist;
00074         huff->freelist = (node_t **)*tppnode;
00075         return tppnode;
00076     }
00077 }

void Huff_addRef (  huff_t *  huff,
byte  ch
) 
 

Definition at line 186 of file huffman.c.

References huff_t::blocNode, byte, ch, get_ppnode(), increment(), huff_t::lhead, huff_t::loc, node_s::next, node_t, huff_t::nodeList, node_s::parent, and huff_t::tree.

Referenced by Huff_Compress(), Huff_Decompress(), and MSG_initHuffman().

00186                                         {
00187     node_t *tnode, *tnode2;
00188     if (huff->loc[ch] == NULL) { /* if this is the first transmission of this node */
00189         tnode = &(huff->nodeList[huff->blocNode++]);
00190         tnode2 = &(huff->nodeList[huff->blocNode++]);
00191 
00192         tnode2->symbol = INTERNAL_NODE;
00193         tnode2->weight = 1;
00194         tnode2->next = huff->lhead->next;
00195         if (huff->lhead->next) {
00196             huff->lhead->next->prev = tnode2;
00197             if (huff->lhead->next->weight == 1) {
00198                 tnode2->head = huff->lhead->next->head;
00199             } else {
00200                 tnode2->head = get_ppnode(huff);
00201                 *tnode2->head = tnode2;
00202             }
00203         } else {
00204             tnode2->head = get_ppnode(huff);
00205             *tnode2->head = tnode2;
00206         }
00207         huff->lhead->next = tnode2;
00208         tnode2->prev = huff->lhead;
00209  
00210         tnode->symbol = ch;
00211         tnode->weight = 1;
00212         tnode->next = huff->lhead->next;
00213         if (huff->lhead->next) {
00214             huff->lhead->next->prev = tnode;
00215             if (huff->lhead->next->weight == 1) {
00216                 tnode->head = huff->lhead->next->head;
00217             } else {
00218                 /* this should never happen */
00219                 tnode->head = get_ppnode(huff);
00220                 *tnode->head = tnode2;
00221             }
00222         } else {
00223             /* this should never happen */
00224             tnode->head = get_ppnode(huff);
00225             *tnode->head = tnode;
00226         }
00227         huff->lhead->next = tnode;
00228         tnode->prev = huff->lhead;
00229         tnode->left = tnode->right = NULL;
00230  
00231         if (huff->lhead->parent) {
00232             if (huff->lhead->parent->left == huff->lhead) { /* lhead is guaranteed to by the NYT */
00233                 huff->lhead->parent->left = tnode2;
00234             } else {
00235                 huff->lhead->parent->right = tnode2;
00236             }
00237         } else {
00238             huff->tree = tnode2; 
00239         }
00240  
00241         tnode2->right = tnode;
00242         tnode2->left = huff->lhead;
00243  
00244         tnode2->parent = huff->lhead->parent;
00245         huff->lhead->parent = tnode->parent = tnode2;
00246      
00247         huff->loc[ch] = tnode;
00248  
00249         increment(huff, tnode2->parent);
00250     } else {
00251         increment(huff, huff->loc[ch]);
00252     }
00253 }

Here is the call graph for this function:

void Huff_Compress (  msg_t *  mbuf,
int  offset
) 
 

Definition at line 378 of file huffman.c.

References bloc, huff_t::blocNode, buffer, byte, ch, Com_Memcpy(), Com_Memset(), msg_t::cursize, msg_t::data, Huff_addRef(), Huff_transmit(), i, huff_t::lhead, huff_t::loc, node_s::next, huff_t::nodeList, offset, node_s::parent, and huff_t::tree.

Referenced by NET_OutOfBandData().

00378                                             {
00379     int         i, ch, size;
00380     byte        seq[65536];
00381     byte*       buffer;
00382     huff_t      huff;
00383 
00384     size = mbuf->cursize - offset;
00385     buffer = mbuf->data+ + offset;
00386 
00387     if (size<=0) {
00388         return;
00389     }
00390 
00391     Com_Memset(&huff, 0, sizeof(huff_t));
00392     // Add the NYT (not yet transmitted) node into the tree/list */
00393     huff.tree = huff.lhead = huff.loc[NYT] =  &(huff.nodeList[huff.blocNode++]);
00394     huff.tree->symbol = NYT;
00395     huff.tree->weight = 0;
00396     huff.lhead->next = huff.lhead->prev = NULL;
00397     huff.tree->parent = huff.tree->left = huff.tree->right = NULL;
00398     huff.loc[NYT] = huff.tree;
00399 
00400     seq[0] = (size>>8);
00401     seq[1] = size&0xff;
00402 
00403     bloc = 16;
00404 
00405     for (i=0; i<size; i++ ) {
00406         ch = buffer[i];
00407         Huff_transmit(&huff, ch, seq);                      /* Transmit symbol */
00408         Huff_addRef(&huff, (byte)ch);                               /* Do update */
00409     }
00410 
00411     bloc += 8;                                              // next byte
00412 
00413     mbuf->cursize = (bloc>>3) + offset;
00414     Com_Memcpy(mbuf->data+offset, seq, (bloc>>3));
00415 }

Here is the call graph for this function:

void Huff_Decompress (  msg_t *  mbuf,
int  offset
) 
 

Definition at line 324 of file huffman.c.

References bloc, huff_t::blocNode, buffer, byte, ch, Com_Memcpy(), Com_Memset(), msg_t::cursize, msg_t::data, get_bit(), Huff_addRef(), Huff_Receive(), i, j, huff_t::lhead, huff_t::loc, huff_t::ltail, msg_t::maxsize, node_s::next, huff_t::nodeList, offset, node_s::parent, and huff_t::tree.

Referenced by SV_ConnectionlessPacket().

00324                                               {
00325     int         ch, cch, i, j, size;
00326     byte        seq[65536];
00327     byte*       buffer;
00328     huff_t      huff;
00329 
00330     size = mbuf->cursize - offset;
00331     buffer = mbuf->data + offset;
00332 
00333     if ( size <= 0 ) {
00334         return;
00335     }
00336 
00337     Com_Memset(&huff, 0, sizeof(huff_t));
00338     // Initialize the tree & list with the NYT node 
00339     huff.tree = huff.lhead = huff.ltail = huff.loc[NYT] = &(huff.nodeList[huff.blocNode++]);
00340     huff.tree->symbol = NYT;
00341     huff.tree->weight = 0;
00342     huff.lhead->next = huff.lhead->prev = NULL;
00343     huff.tree->parent = huff.tree->left = huff.tree->right = NULL;
00344 
00345     cch = buffer[0]*256 + buffer[1];
00346     // don't overflow with bad messages
00347     if ( cch > mbuf->maxsize - offset ) {
00348         cch = mbuf->maxsize - offset;
00349     }
00350     bloc = 16;
00351 
00352     for ( j = 0; j < cch; j++ ) {
00353         ch = 0;
00354         // don't overflow reading from the messages
00355         // FIXME: would it be better to have a overflow check in get_bit ?
00356         if ( (bloc >> 3) > size ) {
00357             seq[j] = 0;
00358             break;
00359         }
00360         Huff_Receive(huff.tree, &ch, buffer);               /* Get a character */
00361         if ( ch == NYT ) {                              /* We got a NYT, get the symbol associated with it */
00362             ch = 0;
00363             for ( i = 0; i < 8; i++ ) {
00364                 ch = (ch<<1) + get_bit(buffer);
00365             }
00366         }
00367     
00368         seq[j] = ch;                                    /* Write symbol */
00369 
00370         Huff_addRef(&huff, (byte)ch);                               /* Increment node */
00371     }
00372     mbuf->cursize = cch + offset;
00373     Com_Memcpy(mbuf->data + offset, seq, cch);
00374 }

Here is the call graph for this function:

int Huff_getBit (  byte *  fin,
int *  offset
) 
 

Definition at line 42 of file huffman.c.

References bloc, byte, offset, and t.

Referenced by MSG_ReadBits().

00042                                              {
00043     int t;
00044     bloc = *offset;
00045     t = (fin[(bloc>>3)] >> (bloc&7)) & 0x1;
00046     bloc++;
00047     *offset = bloc;
00048     return t;
00049 }

void Huff_Init (  huffman_t *  huff  ) 
 

Definition at line 417 of file huffman.c.

References huff_t::blocNode, Com_Memset(), huffman_t::compressor, huffman_t::decompressor, huff_t::lhead, huff_t::loc, huff_t::ltail, node_s::next, huff_t::nodeList, node_s::parent, and huff_t::tree.

Referenced by MSG_initHuffman().

00417                                 {
00418 
00419     Com_Memset(&huff->compressor, 0, sizeof(huff_t));
00420     Com_Memset(&huff->decompressor, 0, sizeof(huff_t));
00421 
00422     // Initialize the tree & list with the NYT node 
00423     huff->decompressor.tree = huff->decompressor.lhead = huff->decompressor.ltail = huff->decompressor.loc[NYT] = &(huff->decompressor.nodeList[huff->decompressor.blocNode++]);
00424     huff->decompressor.tree->symbol = NYT;
00425     huff->decompressor.tree->weight = 0;
00426     huff->decompressor.lhead->next = huff->decompressor.lhead->prev = NULL;
00427     huff->decompressor.tree->parent = huff->decompressor.tree->left = huff->decompressor.tree->right = NULL;
00428 
00429     // Add the NYT (not yet transmitted) node into the tree/list */
00430     huff->compressor.tree = huff->compressor.lhead = huff->compressor.loc[NYT] =  &(huff->compressor.nodeList[huff->compressor.blocNode++]);
00431     huff->compressor.tree->symbol = NYT;
00432     huff->compressor.tree->weight = 0;
00433     huff->compressor.lhead->next = huff->compressor.lhead->prev = NULL;
00434     huff->compressor.tree->parent = huff->compressor.tree->left = huff->compressor.tree->right = NULL;
00435     huff->compressor.loc[NYT] = huff->compressor.tree;
00436 }

Here is the call graph for this function:

void Huff_offsetReceive (  node_t *  node,
int *  ch,
byte *  fin,
int *  offset
) 
 

Definition at line 272 of file huffman.c.

References bloc, byte, ch, get_bit(), node_t, and offset.

Referenced by MSG_ReadBits().

00272                                                                         {
00273     bloc = *offset;
00274     while (node && node->symbol == INTERNAL_NODE) {
00275         if (get_bit(fin)) {
00276             node = node->right;
00277         } else {
00278             node = node->left;
00279         }
00280     }
00281     if (!node) {
00282         *ch = 0;
00283         return;
00284 //      Com_Error(ERR_DROP, "Illegal tree!\n");
00285     }
00286     *ch = node->symbol;
00287     *offset = bloc;
00288 }

Here is the call graph for this function:

void Huff_offsetTransmit (  huff_t *  huff,
int  ch,
byte *  fout,
int *  offset
) 
 

Definition at line 318 of file huffman.c.

References bloc, byte, ch, huff_t::loc, NULL, offset, and send().

Referenced by MSG_WriteBits().

00318                                                                          {
00319     bloc = *offset;
00320     send(huff->loc[ch], NULL, fout);
00321     *offset = bloc;
00322 }

Here is the call graph for this function:

void Huff_putBit (  int  bit,
byte *  fout,
int *  offset
) 
 

Definition at line 32 of file huffman.c.

References bloc, byte, and offset.

Referenced by MSG_WriteBits().

00032                                                        {
00033     bloc = *offset;
00034     if ((bloc&7) == 0) {
00035         fout[(bloc>>3)] = 0;
00036     }
00037     fout[(bloc>>3)] |= bit << (bloc&7);
00038     bloc++;
00039     *offset = bloc;
00040 }

int Huff_Receive (  node_t *  node,
int *  ch,
byte *  fin
) 
 

Definition at line 256 of file huffman.c.

References byte, ch, get_bit(), and node_t.

Referenced by Huff_Decompress().

00256                                                     {
00257     while (node && node->symbol == INTERNAL_NODE) {
00258         if (get_bit(fin)) {
00259             node = node->right;
00260         } else {
00261             node = node->left;
00262         }
00263     }
00264     if (!node) {
00265         return 0;
00266 //      Com_Error(ERR_DROP, "Illegal tree!\n");
00267     }
00268     return (*ch = node->symbol);
00269 }

Here is the call graph for this function:

void Huff_transmit (  huff_t *  huff,
int  ch,
byte *  fout
) 
 

Definition at line 305 of file huffman.c.

References add_bit(), byte, ch, i, huff_t::loc, NULL, NYT, and send().

Referenced by Huff_Compress().

00305                                                       {
00306     int i;
00307     if (huff->loc[ch] == NULL) { 
00308         /* node_t hasn't been transmitted, send a NYT, then the symbol */
00309         Huff_transmit(huff, NYT, fout);
00310         for (i = 7; i >= 0; i--) {
00311             add_bit((char)((ch >> i) & 0x1), fout);
00312         }
00313     } else {
00314         send(huff->loc[ch], NULL, fout);
00315     }
00316 }

Here is the call graph for this function:

void increment (  huff_t *  huff,
node_t *  node
)  [static]
 

Definition at line 148 of file huffman.c.

References free_ppnode(), get_ppnode(), node_s::next, node_t, NULL, node_s::parent, swap, and swaplist().

Referenced by Huff_addRef().

00148                                                   {
00149     node_t *lnode;
00150 
00151     if (!node) {
00152         return;
00153     }
00154 
00155     if (node->next != NULL && node->next->weight == node->weight) {
00156         lnode = *node->head;
00157         if (lnode != node->parent) {
00158             swap(huff, lnode, node);
00159         }
00160         swaplist(lnode, node);
00161     }
00162     if (node->prev && node->prev->weight == node->weight) {
00163         *node->head = node->prev;
00164     } else {
00165         *node->head = NULL;
00166         free_ppnode(huff, node->head);
00167     }
00168     node->weight++;
00169     if (node->next && node->next->weight == node->weight) {
00170         node->head = node->next->head;
00171     } else { 
00172         node->head = get_ppnode(huff);
00173         *node->head = node;
00174     }
00175     if (node->parent) {
00176         increment(huff, node->parent);
00177         if (node->prev == node->parent) {
00178             swaplist(node, node->parent);
00179             if (*node->head == node) {
00180                 *node->head = node->parent;
00181             }
00182         }
00183     }
00184 }

Here is the call graph for this function:

void send (  node_t *  node,
node_t *  child,
byte *  fout
)  [static]
 

Definition at line 291 of file huffman.c.

References add_bit(), byte, node_t, and node_s::parent.

Referenced by GLS_Winding(), Huff_offsetTransmit(), Huff_transmit(), and NET_OpenSocks().

00291                                                           {
00292     if (node->parent) {
00293         send(node->parent, node, fout);
00294     }
00295     if (child) {
00296         if (node->right == child) {
00297             add_bit(1, fout);
00298         } else {
00299             add_bit(0, fout);
00300         }
00301     }
00302 }

Here is the call graph for this function:

void swap (  huff_t *  huff,
node_t *  node1,
node_t *  node2
)  [static]
 

Definition at line 85 of file huffman.c.

References node_t, node_s::parent, and huff_t::tree.

00085                                                               { 
00086     node_t *par1, *par2;
00087 
00088     par1 = node1->parent;
00089     par2 = node2->parent;
00090 
00091     if (par1) {
00092         if (par1->left == node1) {
00093             par1->left = node2;
00094         } else {
00095           par1->right = node2;
00096         }
00097     } else {
00098         huff->tree = node2;
00099     }
00100 
00101     if (par2) {
00102         if (par2->left == node2) {
00103             par2->left = node1;
00104         } else {
00105             par2->right = node1;
00106         }
00107     } else {
00108         huff->tree = node1;
00109     }
00110   
00111     node1->parent = par2;
00112     node2->parent = par1;
00113 }

void swaplist (  node_t *  node1,
node_t *  node2
)  [static]
 

Definition at line 116 of file huffman.c.

References node_s::next, and node_t.

Referenced by increment().

00116                                                    {
00117     node_t *par1;
00118 
00119     par1 = node1->next;
00120     node1->next = node2->next;
00121     node2->next = par1;
00122 
00123     par1 = node1->prev;
00124     node1->prev = node2->prev;
00125     node2->prev = par1;
00126 
00127     if (node1->next == node1) {
00128         node1->next = node2;
00129     }
00130     if (node2->next == node2) {
00131         node2->next = node1;
00132     }
00133     if (node1->next) {
00134         node1->next->prev = node1;
00135     }
00136     if (node2->next) {
00137         node2->next->prev = node2;
00138     }
00139     if (node1->prev) {
00140         node1->prev->next = node1;
00141     }
00142     if (node2->prev) {
00143         node2->prev->next = node2;
00144     }
00145 }

Variable Documentation

int bloc = 0 [static]
 

Definition at line 30 of file huffman.c.

Referenced by add_bit(), get_bit(), Huff_Compress(), Huff_Decompress(), Huff_getBit(), Huff_offsetReceive(), Huff_offsetTransmit(), and Huff_putBit().

int oldsize
 

Definition at line 40 of file msg.c.

Generated on Thu Aug 25 14:43:24 2005 for Quake III Arena by  doxygen 1.3.9.1