Compressor.cpp

Go to the documentation of this file.

/*
===========================================================================

Doom 3 GPL Source Code
Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company. 

This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).  

Doom 3 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 3 of the License, or
(at your option) any later version.

Doom 3 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 Doom 3 Source Code.  If not, see <http://www.gnu.org/licenses/>.

In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code.  If not, please request a copy in writing from id Software at the address below.

If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.

===========================================================================
*/
#include "../idlib/precompiled.h"
#pragma hdrstop


/*
=================================================================================

        idCompressor_None

=================================================================================
*/

class idCompressor_None : public idCompressor {
public:
                                        idCompressor_None( void );

        void                    Init( idFile *f, bool compress, int wordLength );
        void                    FinishCompress( void );
        float                   GetCompressionRatio( void ) const;

        const char *    GetName( void );
        const char *    GetFullPath( void );
        int                             Read( void *outData, int outLength );
        int                             Write( const void *inData, int inLength );
        int                             Length( void );
        ID_TIME_T                       Timestamp( void );
        int                             Tell( void );
        void                    ForceFlush( void );
        void                    Flush( void );
        int                             Seek( long offset, fsOrigin_t origin );

protected:
        idFile *                file;
        bool                    compress;
};

/*
================
idCompressor_None::idCompressor_None
================
*/
idCompressor_None::idCompressor_None( void ) {
        file = NULL;
        compress = true;
}

/*
================
idCompressor_None::Init
================
*/
void idCompressor_None::Init( idFile *f, bool compress, int wordLength ) {
        this->file = f;
        this->compress = compress;
}

/*
================
idCompressor_None::FinishCompress
================
*/
void idCompressor_None::FinishCompress( void ) {
}

/*
================
idCompressor_None::GetCompressionRatio
================
*/
float idCompressor_None::GetCompressionRatio( void ) const {
        return 0.0f;
}

/*
================
idCompressor_None::GetName
================
*/
const char *idCompressor_None::GetName( void ) {
        if ( file ) {
                return file->GetName();
        } else {
                return "";
        }
}

/*
================
idCompressor_None::GetFullPath
================
*/
const char *idCompressor_None::GetFullPath( void ) {
        if ( file ) {
                return file->GetFullPath();
        } else {
                return "";
        }
}

/*
================
idCompressor_None::Write
================
*/
int idCompressor_None::Write( const void *inData, int inLength ) {
        if ( compress == false || inLength <= 0 ) {
                return 0;
        }
        return file->Write( inData, inLength );
}

/*
================
idCompressor_None::Read
================
*/
int idCompressor_None::Read( void *outData, int outLength ) {
        if ( compress == true || outLength <= 0 ) {
                return 0;
        }
        return file->Read( outData, outLength );
}

/*
================
idCompressor_None::Length
================
*/
int idCompressor_None::Length( void ) {
        if ( file ) {
                return file->Length();
        } else {
                return 0;
        }
}

/*
================
idCompressor_None::Timestamp
================
*/
ID_TIME_T idCompressor_None::Timestamp( void ) {
        if ( file ) {
                return file->Timestamp();
        } else {
                return 0;
        }
}

/*
================
idCompressor_None::Tell
================
*/
int idCompressor_None::Tell( void ) {
        if ( file ) {
                return file->Tell();
        } else {
                return 0;
        }
}

/*
================
idCompressor_None::ForceFlush
================
*/
void idCompressor_None::ForceFlush( void ) {
        if ( file ) {
                file->ForceFlush();
        }
}

/*
================
idCompressor_None::Flush
================
*/
void idCompressor_None::Flush( void ) {
        if ( file ) {
                file->ForceFlush();
        }
}

/*
================
idCompressor_None::Seek
================
*/
int idCompressor_None::Seek( long offset, fsOrigin_t origin ) {
        common->Error( "cannot seek on idCompressor" );
        return -1;
}


/*
=================================================================================

        idCompressor_BitStream

        Base class for bit stream compression.

=================================================================================
*/

class idCompressor_BitStream : public idCompressor_None {
public:
                                        idCompressor_BitStream( void ) {}

        void                    Init( idFile *f, bool compress, int wordLength );
        void                    FinishCompress( void );
        float                   GetCompressionRatio( void ) const;

        int                             Write( const void *inData, int inLength );
        int                             Read( void *outData, int outLength );

protected:
        byte                    buffer[65536];
        int                             wordLength;

        int                             readTotalBytes;
        int                             readLength;
        int                             readByte;
        int                             readBit;
        const byte *    readData;

        int                             writeTotalBytes;
        int                             writeLength;
        int                             writeByte;
        int                             writeBit;
        byte *                  writeData;

protected:
        void                    InitCompress( const void *inData, const int inLength );
        void                    InitDecompress( void *outData, int outLength );
        void                    WriteBits( int value, int numBits );
        int                             ReadBits( int numBits );
        void                    UnreadBits( int numBits );
        int                             Compare( const byte *src1, int bitPtr1, const byte *src2, int bitPtr2, int maxBits ) const;
};

/*
================
idCompressor_BitStream::Init
================
*/
void idCompressor_BitStream::Init( idFile *f, bool compress, int wordLength ) {

        assert( wordLength >= 1 && wordLength <= 32 );

        this->file = f;
        this->compress = compress;
        this->wordLength = wordLength;

        readTotalBytes = 0;
        readLength = 0;
        readByte = 0;
        readBit = 0;
        readData = NULL;

        writeTotalBytes = 0;
        writeLength = 0;
        writeByte = 0;
        writeBit = 0;
        writeData = NULL;
}

/*
================
idCompressor_BitStream::InitCompress
================
*/
ID_INLINE void idCompressor_BitStream::InitCompress( const void *inData, const int inLength ) {

        readLength = inLength;
        readByte = 0;
        readBit = 0;
        readData = (const byte *) inData;

        if ( !writeLength ) {
                writeLength = sizeof( buffer );
                writeByte = 0;
                writeBit = 0;
                writeData = buffer;
        }
}

/*
================
idCompressor_BitStream::InitDecompress
================
*/
ID_INLINE void idCompressor_BitStream::InitDecompress( void *outData, int outLength ) {

        if ( !readLength ) {
                readLength = file->Read( buffer, sizeof( buffer ) );
                readByte = 0;
                readBit = 0;
                readData = buffer;
        }

        writeLength = outLength;
        writeByte = 0;
        writeBit = 0;
        writeData = (byte *) outData;
}

/*
================
idCompressor_BitStream::WriteBits
================
*/
void idCompressor_BitStream::WriteBits( int value, int numBits ) {
        int put, fraction;

        // Short circuit for writing single bytes at a time
        if ( writeBit == 0 && numBits == 8 && writeByte < writeLength ) {
                writeByte++;
                writeTotalBytes++;
                writeData[writeByte - 1] = value;
                return;
        }


        while( numBits ) {
                if ( writeBit == 0 ) {
                        if ( writeByte >= writeLength ) {
                                if ( writeData == buffer ) {
                                        file->Write( buffer, writeByte );
                                        writeByte = 0;
                                } else {
                                        put = numBits;
                                        writeBit = put & 7;
                                        writeByte += ( put >> 3 ) + ( writeBit != 0 );
                                        writeTotalBytes += ( put >> 3 ) + ( writeBit != 0 );
                                        return;
                                }
                        }
                        writeData[writeByte] = 0;
                        writeByte++;
                        writeTotalBytes++;
                }
                put = 8 - writeBit;
                if ( put > numBits ) {
                        put = numBits;
                }
                fraction = value & ( ( 1 << put ) - 1 );
                writeData[writeByte - 1] |= fraction << writeBit;
                numBits -= put;
                value >>= put;
                writeBit = ( writeBit + put ) & 7;
        }
}

/*
================
idCompressor_BitStream::ReadBits
================
*/
int idCompressor_BitStream::ReadBits( int numBits ) {
        int value, valueBits, get, fraction;

        value = 0;
        valueBits = 0;

        // Short circuit for reading single bytes at a time
        if ( readBit == 0 && numBits == 8 && readByte < readLength ) {
                readByte++;
                readTotalBytes++;
                return readData[readByte - 1];
        }

        while ( valueBits < numBits ) {
                if ( readBit == 0 ) {
                        if ( readByte >= readLength ) {
                                if ( readData == buffer ) {
                                        readLength = file->Read( buffer, sizeof( buffer ) );
                                        readByte = 0;
                                } else {
                                        get = numBits - valueBits;
                                        readBit = get & 7;
                                        readByte += ( get >> 3 ) + ( readBit != 0 );
                                        readTotalBytes += ( get >> 3 ) + ( readBit != 0 );
                                        return value;
                                }
                        }
                        readByte++;
                        readTotalBytes++;
                }
                get = 8 - readBit;
                if ( get > (numBits - valueBits) ) {
                        get = (numBits - valueBits);
                }
                fraction = readData[readByte - 1];
                fraction >>= readBit;
                fraction &= ( 1 << get ) - 1;
                value |= fraction << valueBits;
                valueBits += get;
                readBit = ( readBit + get ) & 7;
        }

        return value;
}

/*
================
idCompressor_BitStream::UnreadBits
================
*/
void idCompressor_BitStream::UnreadBits( int numBits ) {
        readByte -= ( numBits >> 3 );
        readTotalBytes -= ( numBits >> 3 );
        if ( readBit == 0 ) {
                readBit = 8 - ( numBits & 7 );
        } else {
                readBit -= numBits & 7;
                if ( readBit <= 0 ) {
                        readByte--;
                        readTotalBytes--;
                        readBit = ( readBit + 8 ) & 7;
                }
        }
        if ( readByte < 0 ) {
                readByte = 0;
                readBit = 0;
        }
}

/*
================
idCompressor_BitStream::Compare
================
*/
int idCompressor_BitStream::Compare( const byte *src1, int bitPtr1, const byte *src2, int bitPtr2, int maxBits ) const {
        int i;

        // If the two bit pointers are aligned then we can use a faster comparison
        if ( ( bitPtr1 & 7 ) == (bitPtr2 & 7 ) && maxBits > 16 ) {
                const byte *p1 = &src1[bitPtr1 >> 3];
                const byte *p2 = &src2[bitPtr2 >> 3];

                int bits = 0;

                int bitsRemain = maxBits;

                // Compare the first couple bits (if any)
                if ( bitPtr1 & 7 ) {
                        for ( i = (bitPtr1 & 7); i < 8; i++, bits++ ) {
                                if ( ( ( *p1 >> i ) ^ ( *p2 >> i ) ) & 1 ) {
                                        return bits;
                                }
                                bitsRemain--;
                        }
                        p1++;
                        p2++;
                }

                int remain = bitsRemain >> 3;

                // Compare the middle bytes as ints
                while ( remain >= 4 && (*(const int *)p1 == *(const int *)p2) ) {
                        p1 += 4;
                        p2 += 4;
                        remain -= 4;
                        bits += 32;
                }

                // Compare the remaining bytes
                while ( remain > 0 && (*p1 == *p2) ) {
                        p1++;
                        p2++;
                        remain--;
                        bits += 8;
                }

                // Compare the last couple of bits (if any)
                int finalBits = 8;
                if ( remain == 0 ) {
                        finalBits = ( bitsRemain & 7 );
                }
                for ( i = 0; i < finalBits; i++, bits++ ) {
                        if ( ( ( *p1 >> i ) ^ ( *p2 >> i ) ) & 1 ) {
                                return bits;
                        }
                }

                assert(bits == maxBits);
                return bits;
        } else {
        for ( i = 0; i < maxBits; i++ ) {
                        if ( ( ( src1[bitPtr1 >> 3] >> ( bitPtr1 & 7 ) ) ^ ( src2[bitPtr2 >> 3] >> ( bitPtr2 & 7 ) ) ) & 1 ) {
                        break;
                }
                bitPtr1++;
                bitPtr2++;
        }
        return i;
}
}

/*
================
idCompressor_BitStream::Write
================
*/
int idCompressor_BitStream::Write( const void *inData, int inLength ) {
        int i;

        if ( compress == false || inLength <= 0 ) {
                return 0;
        }

        InitCompress( inData, inLength );

        for ( i = 0; i < inLength; i++ ) {
                WriteBits( ReadBits( 8 ), 8 );
        }
        return i;
}

/*
================
idCompressor_BitStream::FinishCompress
================
*/
void idCompressor_BitStream::FinishCompress( void ) {
        if ( compress == false ) {
                return;
        }

        if ( writeByte ) {
                file->Write( buffer, writeByte );
        }
        writeLength = 0;
        writeByte = 0;
        writeBit = 0;
}

/*
================
idCompressor_BitStream::Read
================
*/
int idCompressor_BitStream::Read( void *outData, int outLength ) {
        int i;

        if ( compress == true || outLength <= 0 ) {
                return 0;
        }

        InitDecompress( outData, outLength );

        for ( i = 0; i < outLength && readLength >= 0; i++ ) {
                WriteBits( ReadBits( 8 ), 8 );
        }
        return i;
}

/*
================
idCompressor_BitStream::GetCompressionRatio
================
*/
float idCompressor_BitStream::GetCompressionRatio( void ) const {
        if ( compress ) {
                return ( readTotalBytes - writeTotalBytes ) * 100.0f / readTotalBytes;
        } else {
                return ( writeTotalBytes - readTotalBytes ) * 100.0f / writeTotalBytes;
        }
}


/*
=================================================================================

        idCompressor_RunLength

        The following algorithm implements run length compression with an arbitrary
        word size.

=================================================================================
*/

class idCompressor_RunLength : public idCompressor_BitStream {
public:
                                        idCompressor_RunLength( void ) {}

        void                    Init( idFile *f, bool compress, int wordLength );

        int                             Write( const void *inData, int inLength );
        int                             Read( void *outData, int outLength );

private:
        int                             runLengthCode;
};

/*
================
idCompressor_RunLength::Init
================
*/
void idCompressor_RunLength::Init( idFile *f, bool compress, int wordLength ) {
        idCompressor_BitStream::Init( f, compress, wordLength );
        runLengthCode = ( 1 << wordLength ) - 1;
}

/*
================
idCompressor_RunLength::Write
================
*/
int idCompressor_RunLength::Write( const void *inData, int inLength ) {
        int bits, nextBits, count;

        if ( compress == false || inLength <= 0 ) {
                return 0;
        }

        InitCompress( inData, inLength );

        while( readByte <= readLength ) {
                count = 1;
                bits = ReadBits( wordLength );
                for ( nextBits = ReadBits( wordLength ); nextBits == bits; nextBits = ReadBits( wordLength ) ) {
                        count++;
                        if ( count >= ( 1 << wordLength ) ) {
                                if ( count >= ( 1 << wordLength ) + 3 || bits == runLengthCode ) {
                                        break;
                                }
                        }
                }
                if ( nextBits != bits ) {
                        UnreadBits( wordLength );
                }
                if ( count > 3 || bits == runLengthCode ) {
                        WriteBits( runLengthCode, wordLength );
                        WriteBits( bits, wordLength );
                        if ( bits != runLengthCode ) {
                                count -= 3;
                        }
                        WriteBits( count - 1, wordLength );
                } else {
                        while( count-- ) {
                                WriteBits( bits, wordLength );
                        }
                }
        }

        return inLength;
}

/*
================
idCompressor_RunLength::Read
================
*/
int idCompressor_RunLength::Read( void *outData, int outLength ) {
        int bits, count;

        if ( compress == true || outLength <= 0 ) {
                return 0;
        }

        InitDecompress( outData, outLength );

        while( writeByte <= writeLength && readLength >= 0 ) {
                bits = ReadBits( wordLength );
                if ( bits == runLengthCode ) {
                        bits = ReadBits( wordLength );
                        count = ReadBits( wordLength ) + 1;
                        if ( bits != runLengthCode ) {
                                count += 3;
                        }
                        while( count-- ) {
                                WriteBits( bits, wordLength );
                        }
                } else {
                        WriteBits( bits, wordLength );
                }
        }

        return writeByte;
}


/*
=================================================================================

        idCompressor_RunLength_ZeroBased

        The following algorithm implements run length compression with an arbitrary
        word size for data with a lot of zero bits.

=================================================================================
*/

class idCompressor_RunLength_ZeroBased : public idCompressor_BitStream {
public:
                                        idCompressor_RunLength_ZeroBased( void ) {}

        int                             Write( const void *inData, int inLength );
        int                             Read( void *outData, int outLength );

private:
};

/*
================
idCompressor_RunLength_ZeroBased::Write
================
*/
int idCompressor_RunLength_ZeroBased::Write( const void *inData, int inLength ) {
        int bits, count;

        if ( compress == false || inLength <= 0 ) {
                return 0;
        }

        InitCompress( inData, inLength );

        while( readByte <= readLength ) {
                count = 0;
                for ( bits = ReadBits( wordLength ); bits == 0 && count < ( 1 << wordLength ); bits = ReadBits( wordLength ) ) {
                        count++;
                }
                if ( count ) {
                        WriteBits( 0, wordLength );
                        WriteBits( count - 1, wordLength );
                        UnreadBits( wordLength );
                } else {
                        WriteBits( bits, wordLength );
                }
        }

        return inLength;
}

/*
================
idCompressor_RunLength_ZeroBased::Read
================
*/
int idCompressor_RunLength_ZeroBased::Read( void *outData, int outLength ) {
        int bits, count;

        if ( compress == true || outLength <= 0 ) {
                return 0;
        }

        InitDecompress( outData, outLength );

        while( writeByte <= writeLength && readLength >= 0 ) {
                bits = ReadBits( wordLength );
                if ( bits == 0 ) {
                        count = ReadBits( wordLength ) + 1;
                        while( count-- > 0 ) {
                                WriteBits( 0, wordLength );
                        }
                } else {
                        WriteBits( bits, wordLength );
                }
        }

        return writeByte;
}


/*
=================================================================================

        idCompressor_Huffman

        The following algorithm 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

=================================================================================
*/

const int HMAX                  = 256;                          // Maximum symbol
const int NYT                   = HMAX;                         // NYT = Not Yet Transmitted
const int INTERNAL_NODE = HMAX + 1;                     // internal node

typedef struct nodetype {
        struct nodetype *left, *right, *parent; // tree structure
        struct nodetype *next, *prev;                   // doubly-linked list
        struct nodetype **head;                                 // highest ranked node in block
        int                             weight;
        int                             symbol; 
} huffmanNode_t;

class idCompressor_Huffman : public idCompressor_None {
public:
                                        idCompressor_Huffman( void ) {}

        void                    Init( idFile *f, bool compress, int wordLength );
        void                    FinishCompress( void );
        float                   GetCompressionRatio( void ) const;

        int                             Write( const void *inData, int inLength );
        int                             Read( void *outData, int outLength );

private:
        byte                    seq[65536];
        int                             bloc;
        int                             blocMax;
        int                             blocIn;
        int                             blocNode;
        int                             blocPtrs;

        int                             compressedSize;
        int                             unCompressedSize;

        huffmanNode_t * tree;
        huffmanNode_t * lhead;
        huffmanNode_t * ltail;
        huffmanNode_t * loc[HMAX+1];
        huffmanNode_t **freelist;

        huffmanNode_t   nodeList[768];
        huffmanNode_t * nodePtrs[768];

private:
        void                    AddRef( byte ch );
        int                             Receive( huffmanNode_t *node, int *ch );
        void                    Transmit( int ch, byte *fout );
        void                    PutBit( int bit, byte *fout, int *offset );
        int                             GetBit( byte *fout, int *offset );

        void                    Add_bit( char bit, byte *fout );
        int                             Get_bit();
        huffmanNode_t **Get_ppnode();
        void                    Free_ppnode( huffmanNode_t **ppnode );
        void                    Swap( huffmanNode_t *node1, huffmanNode_t *node2 );
        void                    Swaplist( huffmanNode_t *node1, huffmanNode_t *node2 );
        void                    Increment( huffmanNode_t *node );
        void                    Send( huffmanNode_t *node, huffmanNode_t *child, byte *fout );
};

/*
================
idCompressor_Huffman::Init
================
*/
void idCompressor_Huffman::Init( idFile *f, bool compress, int wordLength ) {
        int i;

        this->file = f;
        this->compress = compress;
        bloc = 0;
        blocMax = 0;
        blocIn = 0;
        blocNode = 0;
        blocPtrs = 0;
        compressedSize = 0;
        unCompressedSize = 0;

        tree = NULL;
        lhead = NULL;
        ltail = NULL;
        for( i = 0; i < (HMAX+1); i++ ) {
                loc[i] = NULL;
        }
        freelist = NULL;

        for( i = 0; i < 768; i++ ) {
                memset( &nodeList[i], 0, sizeof(huffmanNode_t) );
                nodePtrs[i] = NULL;
        }

        if ( compress ) {
                // Add the NYT (not yet transmitted) node into the tree/list
                tree = lhead = loc[NYT] = &nodeList[blocNode++];
                tree->symbol = NYT;
                tree->weight = 0;
                lhead->next = lhead->prev = NULL;
                tree->parent = tree->left = tree->right = NULL;
                loc[NYT] = tree;
        } else {
                // Initialize the tree & list with the NYT node 
                tree = lhead = ltail = loc[NYT] = &nodeList[blocNode++];
                tree->symbol = NYT;
                tree->weight = 0;
                lhead->next = lhead->prev = NULL;
                tree->parent = tree->left = tree->right = NULL;
        }
}

/*
================
idCompressor_Huffman::PutBit
================
*/
void idCompressor_Huffman::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;
}

/*
================
idCompressor_Huffman::GetBit
================
*/
int idCompressor_Huffman::GetBit( byte *fin, int *offset) {
        int t;
        bloc = *offset;
        t = (fin[(bloc>>3)] >> (bloc&7)) & 0x1;
        bloc++;
        *offset = bloc;
        return t;
}

/*
================
idCompressor_Huffman::Add_bit

  Add a bit to the output file (buffered)
================
*/
void idCompressor_Huffman::Add_bit( char bit, byte *fout ) {
        if ( (bloc&7) == 0 ) {
                fout[(bloc>>3)] = 0;
        }
        fout[(bloc>>3)] |= bit << (bloc&7);
        bloc++;
}

/*
================
idCompressor_Huffman::Get_bit

  Get one bit from the input file (buffered)
================
*/
int idCompressor_Huffman::Get_bit() {
        int t;
        int wh = bloc >> 3;
        int whb = wh>> 16;
        if ( whb != blocIn ) {
                blocMax += file->Read( seq, sizeof( seq ) );
                blocIn++;
        }
        wh &= 0xffff;
        t = ( seq[wh] >> ( bloc & 7 ) ) & 0x1;
        bloc++;
        return t;
}

/*
================
idCompressor_Huffman::Get_ppnode
================
*/
huffmanNode_t **idCompressor_Huffman::Get_ppnode() {
        huffmanNode_t **tppnode;
        if ( !freelist ) {
                return &nodePtrs[blocPtrs++];
        } else {
                tppnode = freelist;
                freelist = (huffmanNode_t **)*tppnode;
                return tppnode;
        }
}

/*
================
idCompressor_Huffman::Free_ppnode
================
*/
void idCompressor_Huffman::Free_ppnode( huffmanNode_t **ppnode ) {
        *ppnode = (huffmanNode_t *)freelist;
        freelist = ppnode;
}

/*
================
idCompressor_Huffman::Swap

  Swap the location of the given two nodes in the tree.
================
*/
void idCompressor_Huffman::Swap( huffmanNode_t *node1, huffmanNode_t *node2 ) { 
        huffmanNode_t *par1, *par2;

        par1 = node1->parent;
        par2 = node2->parent;

        if ( par1 ) {
                if ( par1->left == node1 ) {
                        par1->left = node2;
                } else {
              par1->right = node2;
                }
        } else {
                tree = node2;
        }

        if ( par2 ) {
                if ( par2->left == node2 ) {
                        par2->left = node1;
                } else {
                        par2->right = node1;
                }
        } else {
                tree = node1;
        }
  
        node1->parent = par2;
        node2->parent = par1;
}

/*
================
idCompressor_Huffman::Swaplist

  Swap the given two nodes in the linked list (update ranks)
================
*/
void idCompressor_Huffman::Swaplist( huffmanNode_t *node1, huffmanNode_t *node2 ) {
        huffmanNode_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;
        }
}

/*
================
idCompressor_Huffman::Increment
================
*/
void idCompressor_Huffman::Increment( huffmanNode_t *node ) {
        huffmanNode_t *lnode;

        if ( !node ) {
                return;
        }

        if ( node->next != NULL && node->next->weight == node->weight ) {
            lnode = *node->head;
                if ( lnode != node->parent ) {
                        Swap( lnode, node );
                }
                Swaplist( lnode, node );
        }
        if ( node->prev && node->prev->weight == node->weight ) {
                *node->head = node->prev;
        } else {
            *node->head = NULL;
                Free_ppnode( node->head );
        }
        node->weight++;
        if ( node->next && node->next->weight == node->weight ) {
                node->head = node->next->head;
        } else { 
                node->head = Get_ppnode();
                *node->head = node;
        }
        if ( node->parent ) {
                Increment( node->parent );
                if ( node->prev == node->parent ) {
                        Swaplist( node, node->parent );
                        if ( *node->head == node ) {
                                *node->head = node->parent;
                        }
                }
        }
}

/*
================
idCompressor_Huffman::AddRef
================
*/
void idCompressor_Huffman::AddRef( byte ch ) {
        huffmanNode_t *tnode, *tnode2;
        if ( loc[ch] == NULL ) { /* if this is the first transmission of this node */
                tnode = &nodeList[blocNode++];
                tnode2 = &nodeList[blocNode++];

                tnode2->symbol = INTERNAL_NODE;
                tnode2->weight = 1;
                tnode2->next = lhead->next;
                if ( lhead->next ) {
                        lhead->next->prev = tnode2;
                        if ( lhead->next->weight == 1 ) {
                                tnode2->head = lhead->next->head;
                        } else {
                                tnode2->head = Get_ppnode();
                                *tnode2->head = tnode2;
                        }
                } else {
                        tnode2->head = Get_ppnode();
                        *tnode2->head = tnode2;
                }
                lhead->next = tnode2;
                tnode2->prev = lhead;
 
                tnode->symbol = ch;
                tnode->weight = 1;
                tnode->next = lhead->next;
                if ( lhead->next ) {
                        lhead->next->prev = tnode;
                        if ( lhead->next->weight == 1 ) {
                                tnode->head = lhead->next->head;
                        } else {
                                /* this should never happen */
                                tnode->head = Get_ppnode();
                                *tnode->head = tnode2;
                    }
                } else {
                        /* this should never happen */
                        tnode->head = Get_ppnode();
                        *tnode->head = tnode;
                }
                lhead->next = tnode;
                tnode->prev = lhead;
                tnode->left = tnode->right = NULL;
 
                if ( lhead->parent ) {
                        if ( lhead->parent->left == lhead ) { /* lhead is guaranteed to by the NYT */
                                lhead->parent->left = tnode2;
                        } else {
                                lhead->parent->right = tnode2;
                        }
                } else {
                        tree = tnode2; 
                }
 
                tnode2->right = tnode;
                tnode2->left = lhead;
 
                tnode2->parent = lhead->parent;
                lhead->parent = tnode->parent = tnode2;
     
                loc[ch] = tnode;
 
                Increment( tnode2->parent );
        } else {
                Increment( loc[ch] );
        }
}

/*
================
idCompressor_Huffman::Receive

  Get a symbol.
================
*/
int idCompressor_Huffman::Receive( huffmanNode_t *node, int *ch ) {
        while ( node && node->symbol == INTERNAL_NODE ) {
                if ( Get_bit() ) {
                        node = node->right;
                } else {
                        node = node->left;
                }
        }
        if ( !node ) {
                return 0;
        }
        return (*ch = node->symbol);
}

/*
================
idCompressor_Huffman::Send

  Send the prefix code for this node.
================
*/
void idCompressor_Huffman::Send( huffmanNode_t *node, huffmanNode_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 );
                }
        }
}

/*
================
idCompressor_Huffman::Transmit

  Send a symbol.
================
*/
void idCompressor_Huffman::Transmit( int ch, byte *fout ) {
        int i;
        if ( loc[ch] == NULL ) { 
                /* huffmanNode_t hasn't been transmitted, send a NYT, then the symbol */
                Transmit( NYT, fout );
                for ( i = 7; i >= 0; i-- ) {
                        Add_bit( (char)((ch >> i) & 0x1), fout );
                }
        } else {
                Send( loc[ch], NULL, fout );
        }
}

/*
================
idCompressor_Huffman::Write
================
*/
int idCompressor_Huffman::Write( const void *inData, int inLength ) {
        int i, ch;

        if ( compress == false || inLength <= 0 ) {
                return 0;
        }

        for ( i = 0; i < inLength; i++ ) {
                ch = ((const byte *)inData)[i];
                Transmit( ch, seq );                            /* Transmit symbol */
                AddRef( (byte)ch );                                     /* Do update */
                int b = (bloc>>3);
                if ( b > 32768 ) {
                        file->Write( seq, b );
                        seq[0] = seq[b];
                        bloc &= 7;
                        compressedSize += b;
                }
        }

        unCompressedSize += i;
        return i;
}

/*
================
idCompressor_Huffman::FinishCompress
================
*/
void idCompressor_Huffman::FinishCompress( void ) {

        if ( compress == false ) {
                return;
        }
        
        bloc += 7;
        int str = (bloc>>3);
        if ( str ) {
                file->Write( seq, str );
                compressedSize += str;
        }
}

/*
================
idCompressor_Huffman::Read
================
*/
int idCompressor_Huffman::Read( void *outData, int outLength ) {
        int i, j, ch;

        if ( compress == true || outLength <= 0 ) {
                return 0;
        }

        if ( bloc == 0 ) {
                blocMax = file->Read( seq, sizeof( seq ) );
                blocIn = 0;
        }

        for ( i = 0; i < outLength; i++ ) {
                ch = 0;
                // don't overflow reading from the file
                if ( ( bloc >> 3 ) > blocMax ) {
                        break;
                }
                Receive( tree, &ch );                           /* Get a character */
                if ( ch == NYT ) {                                      /* We got a NYT, get the symbol associated with it */
                        ch = 0;
                        for ( j = 0; j < 8; j++ ) {
                                ch = ( ch << 1 ) + Get_bit();
                        }
                }
    
                ((byte *)outData)[i] = ch;                      /* Write symbol */
                AddRef( (byte) ch );                            /* Increment node */
        }

        compressedSize = bloc >> 3;
        unCompressedSize += i;
        return i;
}

/*
================
idCompressor_Huffman::GetCompressionRatio
================
*/
float idCompressor_Huffman::GetCompressionRatio( void ) const {
        return ( unCompressedSize - compressedSize ) * 100.0f / unCompressedSize;
}


/*
=================================================================================

        idCompressor_Arithmetic

        The following algorithm is based on the Arithmetic Coding methods described
        by Mark Nelson. The probability table is implicitly stored.

=================================================================================
*/

const int AC_WORD_LENGTH        = 8;
const int AC_NUM_BITS           = 16;
const int AC_MSB_SHIFT          = 15;
const int AC_MSB2_SHIFT         = 14;
const int AC_MSB_MASK           = 0x8000;
const int AC_MSB2_MASK          = 0x4000;
const int AC_HIGH_INIT          = 0xffff;
const int AC_LOW_INIT           = 0x0000;

class idCompressor_Arithmetic : public idCompressor_BitStream {
public:
                                        idCompressor_Arithmetic( void ) {}

        void                    Init( idFile *f, bool compress, int wordLength );
        void                    FinishCompress( void );

        int                             Write( const void *inData, int inLength );
        int                             Read( void *outData, int outLength );
        
private:
                                        typedef struct acProbs_s {
                                                unsigned int    low;
                                                unsigned int    high;
                                        } acProbs_t;
                                
                                        typedef struct acSymbol_s {
                                                unsigned int    low;
                                                unsigned int    high;
                                                int                             position;
                                        } acSymbol_t;

        acProbs_t               probabilities[1<<AC_WORD_LENGTH];

        int                             symbolBuffer;
        int                             symbolBit;

        unsigned short  low;
        unsigned short  high;
        unsigned short  code;
        unsigned int    underflowBits;
        unsigned int    scale;

private:
        void                    InitProbabilities( void );
        void                    UpdateProbabilities( acSymbol_t* symbol );
        int                             ProbabilityForCount( unsigned int count );

        void                    CharToSymbol( byte c, acSymbol_t* symbol );
        void                    EncodeSymbol( acSymbol_t* symbol );

        int                             SymbolFromCount( unsigned int count, acSymbol_t* symbol );
        int                             GetCurrentCount( void );
        void                    RemoveSymbolFromStream( acSymbol_t* symbol );

        void                    PutBit( int bit );
        int                             GetBit( void );

        void                    WriteOverflowBits( void );
};

/*
================
idCompressor_Arithmetic::Init
================
*/
void idCompressor_Arithmetic::Init( idFile *f, bool compress, int wordLength ) {
        idCompressor_BitStream::Init( f, compress, wordLength );

        symbolBuffer    = 0;
        symbolBit               = 0;
}

/*
================
idCompressor_Arithmetic::InitProbabilities
================
*/
void idCompressor_Arithmetic::InitProbabilities( void ) {
        high                    = AC_HIGH_INIT;
        low                             = AC_LOW_INIT;
        underflowBits   = 0;
        code                    = 0;

        for( int i = 0; i < (1<<AC_WORD_LENGTH); i++ ) {
                probabilities[ i ].low = i;
                probabilities[ i ].high = i + 1;
        }

        scale = (1<<AC_WORD_LENGTH);
}

/*
================
idCompressor_Arithmetic::UpdateProbabilities
================
*/
void idCompressor_Arithmetic::UpdateProbabilities( acSymbol_t* symbol ) {
        int i, x;

        x = symbol->position;
        
        probabilities[ x ].high++;

        for( i = x + 1; i < (1<<AC_WORD_LENGTH); i++ ) {
                probabilities[ i ].low++;
                probabilities[ i ].high++;
        }

        scale++;
}

/*
================
idCompressor_Arithmetic::GetCurrentCount
================
*/
int idCompressor_Arithmetic::GetCurrentCount( void ) {
    return (unsigned int) ( ( ( ( (long) code - low ) + 1 ) * scale - 1 ) / ( ( (long) high - low ) + 1 ) );
}

/*
================
idCompressor_Arithmetic::ProbabilityForCount
================
*/
int idCompressor_Arithmetic::ProbabilityForCount( unsigned int count ) {
#if 1

        int len, mid, offset, res;

        len = (1<<AC_WORD_LENGTH);
        mid = len;
        offset = 0;
        res = 0;
        while( mid > 0 ) {
                mid = len >> 1;
                if ( count >= probabilities[offset+mid].high ) {
                        offset += mid;
                        len -= mid;
                        res = 1;
                }
                else if ( count < probabilities[offset+mid].low ) {
                        len -= mid;
                        res = 0;
                } else {
                        return offset+mid;
                }
        }
        return offset+res;

#else

        int j;

        for( j = 0; j < (1<<AC_WORD_LENGTH); j++ ) {
        if ( count >= probabilities[ j ].low && count < probabilities[ j ].high ) {
                        return j;
        }
    }

        assert( false );

        return 0;

#endif
}

/*
================
idCompressor_Arithmetic::SymbolFromCount
================
*/
int idCompressor_Arithmetic::SymbolFromCount( unsigned int count, acSymbol_t* symbol ) {
        int p = ProbabilityForCount( count );
    symbol->low = probabilities[ p ].low;
    symbol->high = probabilities[ p ].high;
        symbol->position = p;
    return p;
}

/*
================
idCompressor_Arithmetic::RemoveSymbolFromStream
================
*/
void idCompressor_Arithmetic::RemoveSymbolFromStream( acSymbol_t* symbol ) {
    long range;

        range   = ( long )( high - low ) + 1;
        high    = low + ( unsigned short )( ( range * symbol->high ) / scale - 1 );
        low             = low + ( unsigned short )( ( range * symbol->low ) / scale );

    while( true ) {

        if ( ( high & AC_MSB_MASK ) == ( low & AC_MSB_MASK ) ) {

                } else if( ( low & AC_MSB2_MASK ) == AC_MSB2_MASK && ( high & AC_MSB2_MASK ) == 0 ) {
            code        ^= AC_MSB2_MASK;
            low         &= AC_MSB2_MASK - 1;
            high        |= AC_MSB2_MASK;
                } else {
                        UpdateProbabilities( symbol );
            return;
                }

        low <<= 1;
        high <<= 1;
        high |= 1;
        code <<= 1;
        code |= ReadBits( 1 );
    }
}

/*
================
idCompressor_Arithmetic::GetBit
================
*/
int idCompressor_Arithmetic::GetBit( void ) {
        int getbit;

        if( symbolBit <= 0 ) {
                // read a new symbol out
                acSymbol_t symbol;
                symbolBuffer = SymbolFromCount( GetCurrentCount(), &symbol );
                RemoveSymbolFromStream( &symbol );
                symbolBit = AC_WORD_LENGTH;
        }

        getbit = ( symbolBuffer >> ( AC_WORD_LENGTH - symbolBit ) ) & 1;
        symbolBit--;

        return getbit;
}

/*
================
idCompressor_Arithmetic::EncodeSymbol
================
*/
void idCompressor_Arithmetic::EncodeSymbol( acSymbol_t* symbol ) {
        unsigned int range;
        
        // rescale high and low for the new symbol.
        range   = ( high - low ) + 1;
        high    = low + ( unsigned short )(( range * symbol->high ) / scale - 1 );
        low             = low + ( unsigned short )(( range * symbol->low ) / scale );

        while( true ) {
                if ( ( high & AC_MSB_MASK ) == ( low & AC_MSB_MASK ) ) {
                        // the high digits of low and high have converged, and can be written to the stream
                        WriteBits( high >> AC_MSB_SHIFT, 1 );

            while( underflowBits > 0 ) {

                                WriteBits( ~high >> AC_MSB_SHIFT, 1 );

                                underflowBits--;
            }
        } else if ( ( low & AC_MSB2_MASK ) && !( high & AC_MSB2_MASK ) ) {
                        // underflow is in danger of happening, 2nd digits are converging but 1st digits don't match
                        underflowBits   += 1;
                        low                             &= AC_MSB2_MASK - 1;
                        high                    |= AC_MSB2_MASK;
                } else {
                        UpdateProbabilities( symbol );
            return;
                }

        low <<= 1;
        high <<= 1;
        high |= 1;
    }
}

/*
================
idCompressor_Arithmetic::CharToSymbol
================
*/
void idCompressor_Arithmetic::CharToSymbol( byte c, acSymbol_t* symbol ) {
        symbol->low                     = probabilities[ c ].low;
        symbol->high            = probabilities[ c ].high;
        symbol->position        = c;
}

/*
================
idCompressor_Arithmetic::PutBit
================
*/
void idCompressor_Arithmetic::PutBit( int putbit ) {
        symbolBuffer |= ( putbit & 1 ) << symbolBit;
        symbolBit++;

        if( symbolBit >= AC_WORD_LENGTH ) {
                acSymbol_t symbol;

                CharToSymbol( symbolBuffer, &symbol );
                EncodeSymbol( &symbol );

                symbolBit = 0;
                symbolBuffer = 0;
        }
}

/*
================
idCompressor_Arithmetic::WriteOverflowBits
================
*/
void idCompressor_Arithmetic::WriteOverflowBits( void ) {

        WriteBits( low >> AC_MSB2_SHIFT, 1 );

        underflowBits++;
        while( underflowBits-- > 0 ) {
                WriteBits( ~low >> AC_MSB2_SHIFT, 1 );
        }
}

/*
================
idCompressor_Arithmetic::Write
================
*/
int idCompressor_Arithmetic::Write( const void *inData, int inLength ) {
        int i, j;

        if ( compress == false || inLength <= 0 ) {
                return 0;
        }

        InitCompress( inData, inLength );

        for( i = 0; i < inLength; i++ ) {
                if ( ( readTotalBytes & ( ( 1 << 14 ) - 1 ) ) == 0 ) {
                        if ( readTotalBytes ) {
                                WriteOverflowBits();
                                WriteBits( 0, 15 );
                                while( writeBit ) {
                                        WriteBits( 0, 1 );
                                }
                                WriteBits( 255, 8 );
                        }
                        InitProbabilities();
                }
                for ( j = 0; j < 8; j++ ) {
                        PutBit( ReadBits( 1 ) );
                }
        }

        return inLength;
}

/*
================
idCompressor_Arithmetic::FinishCompress
================
*/
void idCompressor_Arithmetic::FinishCompress( void ) {
        if ( compress == false ) {
                return;
        }

        WriteOverflowBits();

        idCompressor_BitStream::FinishCompress();
}

/*
================
idCompressor_Arithmetic::Read
================
*/
int idCompressor_Arithmetic::Read( void *outData, int outLength ) {
        int i, j;

        if ( compress == true || outLength <= 0 ) {
                return 0;
        }

        InitDecompress( outData, outLength );

        for( i = 0; i < outLength && readLength >= 0; i++ ) {
                if ( ( writeTotalBytes & ( ( 1 << 14 ) - 1 ) ) == 0 ) {
                        if ( writeTotalBytes ) {
                                while( readBit ) {
                                        ReadBits( 1 );
                                }
                                while( ReadBits( 8 ) == 0 && readLength > 0 ) {
                                }
                        }
                        InitProbabilities();
                        for ( j = 0; j < AC_NUM_BITS; j++ ) {
                                code <<= 1;
                                code |= ReadBits( 1 );
                        }
                }
                for ( j = 0; j < 8; j++ ) {
                        WriteBits( GetBit(), 1 );
                }
        }

        return i;
}


/*
=================================================================================

        idCompressor_LZSS

        In 1977 Abraham Lempel and Jacob Ziv presented a dictionary based scheme for
        text compression called LZ77. For any new text LZ77 outputs an offset/length
        pair to previously seen text and the next new byte after the previously seen
        text.

        In 1982 James Storer and Thomas Szymanski presented a modification on the work
        of Lempel and Ziv called LZSS. LZ77 always outputs an offset/length pair, even
        if a match is only one byte long. An offset/length pair usually takes more than
        a single byte to store and the compression is not optimal for small match sizes.
        LZSS uses a bit flag which tells whether the following data is a literal (byte)
        or an offset/length pair.

        The following algorithm is an implementation of LZSS with arbitrary word size.

=================================================================================
*/

const int LZSS_BLOCK_SIZE               = 65535;
const int LZSS_HASH_BITS                = 10;
const int LZSS_HASH_SIZE                = ( 1 << LZSS_HASH_BITS );
const int LZSS_HASH_MASK                = ( 1 << LZSS_HASH_BITS ) - 1;
const int LZSS_OFFSET_BITS              = 11;
const int LZSS_LENGTH_BITS              = 5;

class idCompressor_LZSS : public idCompressor_BitStream {
public:
                                        idCompressor_LZSS( void ) {}

        void                    Init( idFile *f, bool compress, int wordLength );
        void                    FinishCompress( void );

        int                             Write( const void *inData, int inLength );
        int                             Read( void *outData, int outLength );

protected:
        int                             offsetBits;
        int                             lengthBits;
        int                             minMatchWords;

        byte                    block[LZSS_BLOCK_SIZE];
        int                             blockSize;
        int                             blockIndex;

        int                             hashTable[LZSS_HASH_SIZE];
        int                             hashNext[LZSS_BLOCK_SIZE * 8];

protected:
        bool                    FindMatch( int startWord, int startValue, int &wordOffset, int &numWords );
        void                    AddToHash( int index, int hash );
        int                             GetWordFromBlock( int wordOffset ) const;
        virtual void    CompressBlock( void );
        virtual void    DecompressBlock( void );
};

/*
================
idCompressor_LZSS::Init
================
*/
void idCompressor_LZSS::Init( idFile *f, bool compress, int wordLength ) {
        idCompressor_BitStream::Init( f, compress, wordLength );

        offsetBits = LZSS_OFFSET_BITS;
        lengthBits = LZSS_LENGTH_BITS;

        minMatchWords = ( offsetBits + lengthBits + wordLength ) / wordLength;
        blockSize = 0;
        blockIndex = 0;
}

/*
================
idCompressor_LZSS::FindMatch
================
*/
bool idCompressor_LZSS::FindMatch( int startWord, int startValue, int &wordOffset, int &numWords ) {
        int i, n, hash, bottom, maxBits;

        wordOffset = startWord;
        numWords = minMatchWords - 1;

        bottom = Max( 0, startWord - ( ( 1 << offsetBits ) - 1 ) );
        maxBits = ( blockSize << 3 ) - startWord * wordLength;

        hash = startValue & LZSS_HASH_MASK;
        for ( i = hashTable[hash]; i >= bottom; i = hashNext[i] ) {
                n = Compare( block, i * wordLength, block, startWord * wordLength, Min( maxBits, ( startWord - i ) * wordLength ) );
                if ( n > numWords * wordLength ) {
                        numWords = n / wordLength;
                        wordOffset = i;
                        if ( numWords > ( ( 1 << lengthBits ) - 1 + minMatchWords ) - 1 ) {
                                numWords = ( ( 1 << lengthBits ) - 1 + minMatchWords ) - 1;
                                break;
                        }
                }
        }

        return ( numWords >= minMatchWords );
}

/*
================
idCompressor_LZSS::AddToHash
================
*/
void idCompressor_LZSS::AddToHash( int index, int hash ) {
        hashNext[index] = hashTable[hash];
        hashTable[hash] = index;
}

/*
================
idCompressor_LZSS::GetWordFromBlock
================
*/
int idCompressor_LZSS::GetWordFromBlock( int wordOffset ) const {
        int blockBit, blockByte, value, valueBits, get, fraction;

        blockBit = ( wordOffset * wordLength ) & 7;
        blockByte = ( wordOffset * wordLength ) >> 3;
        if ( blockBit != 0 ) {
                blockByte++;
        }

        value = 0;
        valueBits = 0;

        while ( valueBits < wordLength ) {
                if ( blockBit == 0 ) {
                        if ( blockByte >= LZSS_BLOCK_SIZE ) {
                                return value;
                        }
                        blockByte++;
                }
                get = 8 - blockBit;
                if ( get > (wordLength - valueBits) ) {
                        get = (wordLength - valueBits);
                }
                fraction = block[blockByte - 1];
                fraction >>= blockBit;
                fraction &= ( 1 << get ) - 1;
                value |= fraction << valueBits;
                valueBits += get;
                blockBit = ( blockBit + get ) & 7;
        }

        return value;
}

/*
================
idCompressor_LZSS::CompressBlock
================
*/
void idCompressor_LZSS::CompressBlock( void ) {
        int i, startWord, startValue, wordOffset, numWords;

        InitCompress( block, blockSize );

        memset( hashTable, -1, sizeof( hashTable ) );
        memset( hashNext, -1, sizeof( hashNext ) );

        startWord = 0;
        while( readByte < readLength ) {
                startValue = ReadBits( wordLength );
                if ( FindMatch( startWord, startValue, wordOffset, numWords ) ) {
                        WriteBits( 1, 1 );
                        WriteBits( startWord - wordOffset, offsetBits );
                        WriteBits( numWords - minMatchWords, lengthBits );
                        UnreadBits( wordLength );
                        for ( i = 0; i < numWords; i++ ) {
                                startValue = ReadBits( wordLength );
                                AddToHash( startWord, startValue & LZSS_HASH_MASK );
                                startWord++;
                        }
                } else {
                        WriteBits( 0, 1 );
                        WriteBits( startValue, wordLength );
                        AddToHash( startWord, startValue & LZSS_HASH_MASK );
                        startWord++;
                }
        }

        blockSize = 0;
}

/*
================
idCompressor_LZSS::DecompressBlock
================
*/
void idCompressor_LZSS::DecompressBlock( void ) {
        int i, offset, startWord, numWords;

        InitDecompress( block, LZSS_BLOCK_SIZE );

        startWord = 0;
        while( writeByte < writeLength && readLength >= 0 ) {
                if ( ReadBits( 1 ) ) {
                        offset = startWord - ReadBits( offsetBits );
                        numWords = ReadBits( lengthBits ) + minMatchWords;
                        for ( i = 0; i < numWords; i++ ) {
                                WriteBits( GetWordFromBlock( offset + i ), wordLength );
                                startWord++;
                        }
                } else {
                        WriteBits( ReadBits( wordLength ), wordLength );
                        startWord++;
                }
        }

        blockSize = Min( writeByte, LZSS_BLOCK_SIZE );
}

/*
================
idCompressor_LZSS::Write
================
*/
int idCompressor_LZSS::Write( const void *inData, int inLength ) {
        int i, n;

        if ( compress == false || inLength <= 0 ) {
                return 0;
        }

        for ( n = i = 0; i < inLength; i += n ) {
                n = LZSS_BLOCK_SIZE - blockSize;
                if ( inLength - i >= n ) {
                        memcpy( block + blockSize, ((const byte *)inData) + i, n );
                        blockSize = LZSS_BLOCK_SIZE;
                        CompressBlock();
                        blockSize = 0;
                } else {
                        memcpy( block + blockSize, ((const byte *)inData) + i, inLength - i );
                        n = inLength - i;
                        blockSize += n;
                }
        }

        return inLength;
}

/*
================
idCompressor_LZSS::FinishCompress
================
*/
void idCompressor_LZSS::FinishCompress( void ) {
        if ( compress == false ) {
                return;
        }
        if ( blockSize ) {
                CompressBlock();
        }
        idCompressor_BitStream::FinishCompress();
}

/*
================
idCompressor_LZSS::Read
================
*/
int idCompressor_LZSS::Read( void *outData, int outLength ) {
        int i, n;

        if ( compress == true || outLength <= 0 ) {
                return 0;
        }

        if ( !blockSize ) {
                DecompressBlock();
        }

        for ( n = i = 0; i < outLength; i += n ) {
                if ( !blockSize ) {
                        return i;
                }
                n = blockSize - blockIndex;
                if ( outLength - i >= n ) {
                        memcpy( ((byte *)outData) + i, block + blockIndex, n );
                        DecompressBlock();
                        blockIndex = 0;
                } else {
                        memcpy( ((byte *)outData) + i, block + blockIndex, outLength - i );
                        n = outLength - i;
                        blockIndex += n;
                }
        }

        return outLength;
}

/*
=================================================================================

        idCompressor_LZSS_WordAligned

        Outputs word aligned compressed data.

=================================================================================
*/

class idCompressor_LZSS_WordAligned : public idCompressor_LZSS {
public:
                                        idCompressor_LZSS_WordAligned( void ) {}

        void                    Init( idFile *f, bool compress, int wordLength );
private:
        virtual void    CompressBlock( void );
        virtual void    DecompressBlock( void );
};

/*
================
idCompressor_LZSS_WordAligned::Init
================
*/
void idCompressor_LZSS_WordAligned::Init( idFile *f, bool compress, int wordLength ) {
        idCompressor_LZSS::Init( f, compress, wordLength );

        offsetBits = 2 * wordLength;
        lengthBits = wordLength;

        minMatchWords = ( offsetBits + lengthBits + wordLength ) / wordLength;
        blockSize = 0;
        blockIndex = 0;
}

/*
================
idCompressor_LZSS_WordAligned::CompressBlock
================
*/
void idCompressor_LZSS_WordAligned::CompressBlock( void ) {
        int i, startWord, startValue, wordOffset, numWords;

        InitCompress( block, blockSize );

        memset( hashTable, -1, sizeof( hashTable ) );
        memset( hashNext, -1, sizeof( hashNext ) );

        startWord = 0;
        while( readByte < readLength ) {
                startValue = ReadBits( wordLength );
                if ( FindMatch( startWord, startValue, wordOffset, numWords ) ) {
                        WriteBits( numWords - ( minMatchWords - 1 ), lengthBits );
                        WriteBits( startWord - wordOffset, offsetBits );
                        UnreadBits( wordLength );
                        for ( i = 0; i < numWords; i++ ) {
                                startValue = ReadBits( wordLength );
                                AddToHash( startWord, startValue & LZSS_HASH_MASK );
                                startWord++;
                        }
                } else {
                        WriteBits( 0, lengthBits );
                        WriteBits( startValue, wordLength );
                        AddToHash( startWord, startValue & LZSS_HASH_MASK );
                        startWord++;
                }
        }

        blockSize = 0;
}

/*
================
idCompressor_LZSS_WordAligned::DecompressBlock
================
*/
void idCompressor_LZSS_WordAligned::DecompressBlock( void ) {
        int i, offset, startWord, numWords;

        InitDecompress( block, LZSS_BLOCK_SIZE );

        startWord = 0;
        while( writeByte < writeLength && readLength >= 0 ) {
                numWords = ReadBits( lengthBits );
                if ( numWords ) {
                        numWords += ( minMatchWords - 1 );
                        offset = startWord - ReadBits( offsetBits );
                        for ( i = 0; i < numWords; i++ ) {
                                WriteBits( GetWordFromBlock( offset + i ), wordLength );
                                startWord++;
                        }
                } else {
                        WriteBits( ReadBits( wordLength ), wordLength );
                        startWord++;
                }
        }

        blockSize = Min( writeByte, LZSS_BLOCK_SIZE );
}

/*
=================================================================================

        idCompressor_LZW

        http://www.unisys.com/about__unisys/lzw
        http://www.dogma.net/markn/articles/lzw/lzw.htm
        http://www.cs.cf.ac.uk/Dave/Multimedia/node214.html
        http://www.cs.duke.edu/csed/curious/compression/lzw.html
        http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lzw.html

        This is the same compression scheme used by GIF with the exception that
        the EOI and clear codes are not explicitly stored.  Instead EOI happens
        when the input stream runs dry and CC happens when the table gets to big.

        This is a derivation of LZ78, but the dictionary starts with all single
        character values so only code words are output.  It is similar in theory
        to LZ77, but instead of using the previous X bytes as a lookup table, a table
        is built as the stream is read.  The    compressor and decompressor use the
        same formula, so the tables should be exactly alike.  The only catch is the
        decompressor is always one step behind the compressor and may get a code not
        yet in the table.  In this case, it is easy to determine what the next code
        is going to be (it will be the previous string plus the first byte of the
        previous string).

        The dictionary can be any size, but 12 bits seems to produce best results for
        most sample data.  The code size is variable.  It starts with the minimum
        number of bits required to store the dictionary and automatically increases
        as the dictionary gets bigger (it starts at 9 bits and grows to 10 bits when
        item 512 is added, 11 bits when 1024 is added, etc...) once the the dictionary
        is filled (4096 items for a 12 bit dictionary), the whole thing is cleared and
        the process starts over again.

        The compressor increases the bit size after it adds the item, while the
        decompressor does before it adds the item.  The difference is subtle, but
        it's because decompressor being one step behind.  Otherwise, the decompressor
        would read 512 with only 9 bits.

        If "Hello" is in the dictionary, then "Hell", "Hel", "He" and "H" will be too.
        We use this to our advantage by storing the index of the previous code, and
        the value of the last character.  This means when we traverse through the
        dictionary, we get the characters in reverse.

        Dictionary entries 0-255 are always going to have the values 0-255

=================================================================================
*/

class idCompressor_LZW : public idCompressor_BitStream {
public:
                                        idCompressor_LZW( void ) {}

        void                    Init( idFile *f, bool compress, int wordLength );
        void                    FinishCompress( void );

        int                             Write( const void *inData, int inLength );
        int                             Read( void *outData, int outLength );

protected:
        int                             AddToDict( int w, int k );
        int                             Lookup( int w, int k );

        bool                    BumpBits();

        int                             WriteChain( int code );
        void                    DecompressBlock();

        static const int LZW_BLOCK_SIZE = 32767;
        static const int LZW_START_BITS = 9;
        static const int LZW_FIRST_CODE = (1 << (LZW_START_BITS-1));
        static const int LZW_DICT_BITS = 12;
        static const int LZW_DICT_SIZE = 1 << LZW_DICT_BITS;

        // Dictionary data
        struct {
                int k;
                int w;
        }                               dictionary[LZW_DICT_SIZE];
        idHashIndex             index;

        int                             nextCode;
        int                             codeBits;

        // Block data
        byte                    block[LZW_BLOCK_SIZE];
        int                             blockSize;
        int                             blockIndex;

        // Used by the compressor
        int                             w;

        // Used by the decompressor
        int                             oldCode;
};

/*
================
idCompressor_LZW::Init
================
*/
void idCompressor_LZW::Init( idFile *f, bool compress, int wordLength ) {
        idCompressor_BitStream::Init( f, compress, wordLength );

        for ( int i=0; i<LZW_FIRST_CODE; i++ ) {
                dictionary[i].k = i;
                dictionary[i].w = -1;
        }
        index.Clear();

        nextCode = LZW_FIRST_CODE;
        codeBits = LZW_START_BITS;

        blockSize = 0;
        blockIndex = 0;

        w = -1;
        oldCode = -1;
}

/*
================
idCompressor_LZW::Read
================
*/
int idCompressor_LZW::Read( void *outData, int outLength ) {
        int i, n;

        if ( compress == true || outLength <= 0 ) {
                return 0;
        }

        if ( !blockSize ) {
                DecompressBlock();
        }

        for ( n = i = 0; i < outLength; i += n ) {
                if ( !blockSize ) {
                        return i;
                }
                n = blockSize - blockIndex;
                if ( outLength - i >= n ) {
                        memcpy( ((byte *)outData) + i, block + blockIndex, n );
                        DecompressBlock();
                        blockIndex = 0;
                } else {
                        memcpy( ((byte *)outData) + i, block + blockIndex, outLength - i );
                        n = outLength - i;
                        blockIndex += n;
                }
        }

        return outLength;
}

/*
================
idCompressor_LZW::Lookup
================
*/
int idCompressor_LZW::Lookup( int w, int k ) {
        int j;

        if ( w == -1 ) {
                return k;
        } else {
                for ( j = index.First( w ^ k ); j >= 0 ; j = index.Next( j ) ) {
                        if ( dictionary[ j ].k == k && dictionary[ j ].w == w ) { 
                                return j;
                        }
                }
        }

        return -1;
}

/*
================
idCompressor_LZW::AddToDict
================
*/
int idCompressor_LZW::AddToDict( int w, int k ) {
        dictionary[ nextCode ].k = k;
        dictionary[ nextCode ].w = w;
        index.Add( w ^ k, nextCode );
        return nextCode++;
}

/*
================
idCompressor_LZW::BumpBits

Possibly increments codeBits
Returns true if the dictionary was cleared
================
*/
bool idCompressor_LZW::BumpBits() {
        if ( nextCode == ( 1 << codeBits ) ) {
                codeBits ++;
                if ( codeBits > LZW_DICT_BITS ) {
                        nextCode = LZW_FIRST_CODE;
                        codeBits = LZW_START_BITS;
                        index.Clear();
                        return true;
                }
        }
        return false;
}

/*
================
idCompressor_LZW::FinishCompress
================
*/
void idCompressor_LZW::FinishCompress( void ) {
        WriteBits( w, codeBits );
        idCompressor_BitStream::FinishCompress();
}

/*
================
idCompressor_LZW::Write
================
*/
int idCompressor_LZW::Write( const void *inData, int inLength ) {
        int i;

        InitCompress( inData, inLength );

        for ( i = 0; i < inLength; i++ ) {
                int k = ReadBits( 8 );

                int code = Lookup(w, k);
                if ( code >= 0 ) {
                        w = code;
                } else {
                        WriteBits( w, codeBits );
                        if ( !BumpBits() ) {
                                AddToDict( w, k );
                        }
                        w = k;
                }
        }

        return inLength;
}


/*
================
idCompressor_LZW::WriteChain
The chain is stored backwards, so we have to write it to a buffer then output the buffer in reverse
================
*/
int idCompressor_LZW::WriteChain( int code ) {
        byte chain[LZW_DICT_SIZE];
        int firstChar = 0;
        int i = 0;
        do {
                assert( i < LZW_DICT_SIZE-1 && code >= 0 );
                chain[i++] = dictionary[code].k;
                code = dictionary[code].w;
        } while ( code >= 0 );
        firstChar = chain[--i];
        for ( ; i >= 0; i-- ) {
                WriteBits( chain[i], 8 );
        }
        return firstChar;
}

/*
================
idCompressor_LZW::DecompressBlock
================
*/
void idCompressor_LZW::DecompressBlock() {
        int code, firstChar;

        InitDecompress( block, LZW_BLOCK_SIZE );

        while( writeByte < writeLength - LZW_DICT_SIZE && readLength > 0 ) {
                assert( codeBits <= LZW_DICT_BITS );

                code = ReadBits( codeBits );
                if ( readLength == 0 ) {
                        break;
                }

                if ( oldCode == -1 ) {
                        assert( code < 256 );
                        WriteBits( code, 8 );
                        oldCode = code;
                        firstChar = code;
                        continue;
                }

                if ( code >= nextCode ) {
                        assert( code == nextCode );
                        firstChar = WriteChain( oldCode );
                        WriteBits( firstChar, 8 );
                } else {
                        firstChar = WriteChain( code );
                }
                AddToDict( oldCode, firstChar );
                if ( BumpBits() ) {
                        oldCode = -1;
                } else {
                        oldCode = code;
                }
        }

        blockSize = Min( writeByte, LZW_BLOCK_SIZE );
}

/*
=================================================================================

        idCompressor

=================================================================================
*/

/*
================
idCompressor::AllocNoCompression
================
*/
idCompressor * idCompressor::AllocNoCompression( void ) {
        return new idCompressor_None();
}

/*
================
idCompressor::AllocBitStream
================
*/
idCompressor * idCompressor::AllocBitStream( void ) {
        return new idCompressor_BitStream();
}

/*
================
idCompressor::AllocRunLength
================
*/
idCompressor * idCompressor::AllocRunLength( void ) {
        return new idCompressor_RunLength();
}

/*
================
idCompressor::AllocRunLength_ZeroBased
================
*/
idCompressor * idCompressor::AllocRunLength_ZeroBased( void ) {
        return new idCompressor_RunLength_ZeroBased();
}

/*
================
idCompressor::AllocHuffman
================
*/
idCompressor * idCompressor::AllocHuffman( void ) {
        return new idCompressor_Huffman();
}

/*
================
idCompressor::AllocArithmetic
================
*/
idCompressor * idCompressor::AllocArithmetic( void ) {
        return new idCompressor_Arithmetic();
}

/*
================
idCompressor::AllocLZSS
================
*/
idCompressor * idCompressor::AllocLZSS( void ) {
        return new idCompressor_LZSS();
}

/*
================
idCompressor::AllocLZSS_WordAligned
================
*/
idCompressor * idCompressor::AllocLZSS_WordAligned( void ) {
        return new idCompressor_LZSS_WordAligned();
}

/*
================
idCompressor::AllocLZW
================
*/
idCompressor * idCompressor::AllocLZW( void ) {
        return new idCompressor_LZW();
}