DOOM-3-BFG

LightweightCompression.cpp (11886B)

---

 /*
 ===========================================================================
 
 Doom 3 BFG Edition GPL Source Code
 Copyright (C) 1993-2012 id Software LLC, a ZeniMax Media company. 
 
 This file is part of the Doom 3 BFG Edition GPL Source Code ("Doom 3 BFG Edition Source Code").  
 
 Doom 3 BFG Edition 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 BFG Edition 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 BFG Edition Source Code.  If not, see <http://www.gnu.org/licenses/>.
 
 In addition, the Doom 3 BFG Edition 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 BFG Edition 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.
 
 ===========================================================================
 */
 #pragma hdrstop
 #include "../idLib/precompiled.h"
 #include "LightweightCompression.h"
 
 /*
 ========================
 HashIndex
 ========================
 */
 static int HashIndex( int w, int k ) {
 	return ( w ^ k ) & idLZWCompressor::HASH_MASK;
 }
 
 /*
 ========================
 idLZWCompressor::Start
 ========================
 */
 void idLZWCompressor::Start( uint8 * data_, int maxSize_, bool append ) {
 	// Clear hash
 	ClearHash();
 	
 	if ( append ) {
 		assert( lzwData->nextCode > LZW_FIRST_CODE );
 		
 		int originalNextCode = lzwData->nextCode;
 
 		lzwData->nextCode = LZW_FIRST_CODE;
 		
 		// If we are appending, then fill up the hash
 		for ( int i = LZW_FIRST_CODE; i < originalNextCode; i++ ) {
 			AddToDict( lzwData->dictionaryW[i], lzwData->dictionaryK[i] );
 		}
 	
 		assert( originalNextCode == lzwData->nextCode );
 	} else {
 		for ( int i = 0; i < LZW_FIRST_CODE; i++ ) {
 			lzwData->dictionaryK[i] = (uint8)i;
 			lzwData->dictionaryW[i] = 0xFFFF;
 		}
 
 		lzwData->nextCode		= LZW_FIRST_CODE;
 		lzwData->codeBits		= LZW_START_BITS;
 		lzwData->codeWord		= -1;
 		lzwData->tempValue		= 0;
 		lzwData->tempBits		= 0;
 		lzwData->bytesWritten	= 0;
 	}
 		
 	oldCode		= -1;		// Used by DecompressBlock
 	data		= data_;
 
 	blockSize	= 0;
 	blockIndex	= 0;
 	
 	bytesRead	= 0;
 	
 	maxSize		= maxSize_;
 	overflowed	= false;
 
 	savedBytesWritten	= 0;
 	savedCodeWord		= 0;
 	saveCodeBits		= 0;
 	savedTempValue		= 0;
 	savedTempBits		= 0;
 }
 
 /*
 ========================
 idLZWCompressor::ReadBits
 ========================
 */
 int idLZWCompressor::ReadBits( int bits ) {
 	int bitsToRead = bits - lzwData->tempBits;
 	
 	while ( bitsToRead > 0 ) {
 		if ( bytesRead >= maxSize ) {
 			return -1;
 		}
 		lzwData->tempValue |= (uint64)data[bytesRead++] << lzwData->tempBits;
 		lzwData->tempBits += 8;
 		bitsToRead -= 8;
 	}
 	
 	int value = (int)lzwData->tempValue & ( ( 1 << bits ) - 1 );
 	lzwData->tempValue >>= bits;
 	lzwData->tempBits -= bits;
 	
 	return value;
 }
 
 /*
 ========================
 idLZWCompressor::WriteBits
 ========================
 */
 void idLZWCompressor::WriteBits( uint32 value, int bits ) {
 
 	// Queue up bits into temp value
 	lzwData->tempValue |= (uint64)value << lzwData->tempBits;
 	lzwData->tempBits += bits;
 	
 	// Flush 8 bits (1 byte) at a time ( leftovers will get caught in idLZWCompressor::End() )
 	while ( lzwData->tempBits >= 8 ) {
 		if ( lzwData->bytesWritten >= maxSize ) {
 			overflowed = true;
 			return;
 		}
 
 		data[lzwData->bytesWritten++] = (uint8)( lzwData->tempValue & 255 );
 		lzwData->tempValue >>= 8;
 		lzwData->tempBits -= 8;
 	}
 }
 
 /*
 ========================
 idLZWCompressor::WriteChain
  
 The chain is stored backwards, so we have to write it to a buffer then output the buffer in 
 reverse. 
 ========================
 */
 int idLZWCompressor::WriteChain( int code ) {
 	byte chain[lzwCompressionData_t::LZW_DICT_SIZE];
 	int firstChar = 0;
 	int i = 0;
 	do {
 		assert( i < lzwCompressionData_t::LZW_DICT_SIZE && code < lzwCompressionData_t::LZW_DICT_SIZE && code >= 0 );
 		chain[i++] = (byte)lzwData->dictionaryK[code];
 		code = lzwData->dictionaryW[code];
 	} while ( code != 0xFFFF );
 	firstChar = chain[--i];
 	for ( ; i >= 0; i-- ) {
 		block[blockSize++] = chain[i];
 	}
 	return firstChar;
 }
 
 /*
 ========================
 idLZWCompressor::DecompressBlock
 ========================
 */
 void idLZWCompressor::DecompressBlock() {
 	assert( blockIndex == blockSize );		// Make sure we've read all we can
 	
 	blockIndex = 0;
 	blockSize = 0;
 	
 	int firstChar = -1;
 	while ( blockSize < LZW_BLOCK_SIZE - lzwCompressionData_t::LZW_DICT_SIZE ) {
 		assert( lzwData->codeBits <= lzwCompressionData_t::LZW_DICT_BITS );
 
 		int code = ReadBits( lzwData->codeBits );
 		if ( code == -1 ) {
 			break;
 		}
 
 		if ( oldCode == -1 ) {
 			assert( code < 256 );
 			block[blockSize++] = (uint8)code;
 			oldCode = code;
 			firstChar = code;
 			continue;
 		}
 
 		if ( code >= lzwData->nextCode ) {
 			assert( code == lzwData->nextCode );
 			firstChar = WriteChain( oldCode );
 			block[blockSize++] = (uint8)firstChar;
 		} else {
 			firstChar = WriteChain( code );
 		}
 		AddToDict( oldCode, firstChar );
 		if ( BumpBits() ) {
 			oldCode = -1;
 		} else {
 			oldCode = code;
 		}
 	}
 }
 
 /*
 ========================
 idLZWCompressor::ReadByte
 ========================
 */
 int idLZWCompressor::ReadByte( bool ignoreOverflow ) {
 	if ( blockIndex == blockSize ) {
 		DecompressBlock();
 	}
 
 	if ( blockIndex == blockSize ) { //-V581 DecompressBlock() updates these values, the if() isn't redundant
 		if ( !ignoreOverflow ) {
 			overflowed = true;
 			assert( !"idLZWCompressor::ReadByte overflowed!" );
 		}
 		return -1;
 	}
 	
 	return block[blockIndex++];
 }
 
 
 /*
 ========================
 idLZWCompressor::WriteByte
 ========================
 */
 void idLZWCompressor::WriteByte( uint8 value ) {
 	int code = Lookup( lzwData->codeWord, value );
 	if ( code >= 0 ) {
 		lzwData->codeWord = code;
 	} else {
 		WriteBits( lzwData->codeWord, lzwData->codeBits );
 		if ( !BumpBits() ) {
 			AddToDict( lzwData->codeWord, value );
 		}
 		lzwData->codeWord = value;
 	}
 
 	if ( lzwData->bytesWritten >= maxSize - ( lzwData->codeBits + lzwData->tempBits + 7 ) / 8 ) {
 		overflowed = true;	// At any point, if we can't perform an End call, then trigger an overflow
 		return;
 	}
 }
 
 /*
 ========================
 idLZWCompressor::Lookup 
 ========================
 */
 int idLZWCompressor::Lookup( int w, int k ) {
 	if ( w == -1 ) {
 		return k;
 	} else {
 		int i = HashIndex( w, k );
 		
 		for ( int j = hash[i]; j != 0xFFFF; j = nextHash[j] ) {
 			assert( j < lzwCompressionData_t::LZW_DICT_SIZE );
 			if ( lzwData->dictionaryK[j] == k && lzwData->dictionaryW[j] == w ) { 
 				return j;
 			}
 		}
 	}
 	return -1;
 }
 
 /*
 ========================
 idLZWCompressor::AddToDict 
 ========================
 */
 int idLZWCompressor::AddToDict( int w, int k ) {
 	assert( w < 0xFFFF - 1 );
 	assert( k < 256 );
 	assert( lzwData->nextCode < lzwCompressionData_t::LZW_DICT_SIZE );
 	
 	lzwData->dictionaryK[lzwData->nextCode] = (uint8)k;
 	lzwData->dictionaryW[lzwData->nextCode] = (uint16)w;
 	int i = HashIndex( w, k );
 	nextHash[lzwData->nextCode] = hash[i];
 	hash[i] = (uint16)lzwData->nextCode;
 	return lzwData->nextCode++;
 }
 
 /*
 ========================
 idLZWCompressor::BumpBits
  
 Possibly increments codeBits.
 	return: bool	- true, if the dictionary was cleared. 
 ========================
 */
 bool idLZWCompressor::BumpBits() {
 	if ( lzwData->nextCode == ( 1 << lzwData->codeBits ) ) {
 		lzwData->codeBits ++;
 		if ( lzwData->codeBits > lzwCompressionData_t::LZW_DICT_BITS ) {
 			lzwData->nextCode = LZW_FIRST_CODE;
 			lzwData->codeBits = LZW_START_BITS;
 			ClearHash();
 			return true;
 		}
 	}
 	return false;
 }
 
 /*
 ========================
 idLZWCompressor::End
 ========================
 */
 int idLZWCompressor::End() {
 	assert( lzwData->tempBits < 8 );
 	assert( lzwData->bytesWritten < maxSize - ( lzwData->codeBits + lzwData->tempBits + 7 ) / 8 );
 
 	assert( ( Length() > 0 ) == ( lzwData->codeWord != -1 ) );
 
 	if ( lzwData->codeWord != -1 ) {
 		WriteBits( lzwData->codeWord, lzwData->codeBits );
 	}
 
 	if ( lzwData->tempBits > 0 ) {
 		if ( lzwData->bytesWritten >= maxSize ) {
 			overflowed = true;
 			return -1;
 		}
 		data[lzwData->bytesWritten++] = (uint8)lzwData->tempValue & ( ( 1 << lzwData->tempBits ) - 1 );
 	}
 	
 	return Length() > 0 ? Length() : -1;		// Total bytes written (or failure)
 }
 
 /*
 ========================
 idLZWCompressor::Save
 ========================
 */
 void idLZWCompressor::Save() { 
 	assert( !overflowed );
 	// Check and make sure we are at a good spot (can call End)
 	assert( lzwData->bytesWritten < maxSize - ( lzwData->codeBits + lzwData->tempBits + 7 ) / 8 );
 
 	savedBytesWritten	= lzwData->bytesWritten;
 	savedCodeWord		= lzwData->codeWord;
 	saveCodeBits		= lzwData->codeBits;
 	savedTempValue		= lzwData->tempValue;
 	savedTempBits		= lzwData->tempBits;
 }
 
 /*
 ========================
 idLZWCompressor::Restore
 ========================
 */
 void idLZWCompressor::Restore() { 
 	lzwData->bytesWritten	= savedBytesWritten; 
 	lzwData->codeWord		= savedCodeWord;
 	lzwData->codeBits		= saveCodeBits;
 	lzwData->tempValue		= savedTempValue;
 	lzwData->tempBits		= savedTempBits;
 }
 
 /*
 ========================
 idLZWCompressor::ClearHash
 ========================
 */
 void idLZWCompressor::ClearHash() { 
 	memset( hash, 0xFF, sizeof( hash ) ); 
 }
 
 /*
 ========================
 idZeroRunLengthCompressor
 Simple zero based run length encoder/decoder
 ========================
 */
 
 void idZeroRunLengthCompressor::Start( uint8 * dest_, idLZWCompressor * comp_, int maxSize_ ) {
 	zeroCount	= 0;
 	dest		= dest_;
 	comp		= comp_;
 	compressed	= 0;
 	maxSize		= maxSize_;
 }
 
 bool idZeroRunLengthCompressor::WriteRun() {
 	if ( zeroCount > 0 ) {
 		assert( zeroCount <= 255 );
 		if ( compressed + 2 > maxSize ) {
 			maxSize = -1;
 			return false;
 		}
 		if ( comp != NULL ) {
 			comp->WriteByte( 0 );
 			comp->WriteByte( (uint8)zeroCount );
 		} else {
 			*dest++ = 0;
 			*dest++ = (uint8)zeroCount;
 		}
 		compressed += 2;
 		zeroCount = 0;
 	}
 	return true;
 }
 
 bool idZeroRunLengthCompressor::WriteByte( uint8 value ) {
 	if ( value != 0 || zeroCount >= 255 ) {
 		if ( !WriteRun() ) {
 			maxSize = -1;
 			return false;
 		}
 	}
 	
 	if ( value != 0 ) {
 		if ( compressed + 1 > maxSize ) {
 			maxSize = -1;
 			return false;
 		}
 		if ( comp != NULL ) {
 			comp->WriteByte( value );
 		} else {
 			*dest++ = value; 
 		}
 		compressed++;
 	} else {
 		zeroCount++;
 	}
 	
 	return true;
 }
 
 byte idZeroRunLengthCompressor::ReadByte() {
 	// See if we need to possibly read more data
 	if ( zeroCount == 0 ) {
 		int value = ReadInternal();
 		if ( value == -1 ) {
 			assert( 0 );
 		}
 		if ( value != 0 ) {
 			return (byte)value;	// Return non zero values immediately
 		}
 		// Read the number of zeroes
 		zeroCount = ReadInternal();
 	}
 	
 	assert( zeroCount > 0 );
 	
 	zeroCount--;
 	return 0;
 }
 
 void idZeroRunLengthCompressor::ReadBytes( byte * dest, int count ) {
 	for ( int i = 0; i < count; i++ ) {
 		*dest++ = ReadByte();
 	}
 }
 
 void idZeroRunLengthCompressor::WriteBytes( uint8 * src, int count ) {
 	for ( int i = 0; i < count; i++ ) {
 		WriteByte( *src++ );
 	}
 }
 
 int idZeroRunLengthCompressor::End() {
 	WriteRun();
 	if ( maxSize == -1 ) {
 		return -1;
 	}
 	return compressed;
 }
 
 int idZeroRunLengthCompressor::ReadInternal() {
 	compressed++;
 	if ( comp != NULL ) {
 		return comp->ReadByte();
 	}
 	return *dest++;
 }