qc/framework/Compressor.cpp

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

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();
}