LightweightCompression.h (5798B)
1 /* 2 =========================================================================== 3 4 Doom 3 BFG Edition GPL Source Code 5 Copyright (C) 1993-2012 id Software LLC, a ZeniMax Media company. 6 7 This file is part of the Doom 3 BFG Edition GPL Source Code ("Doom 3 BFG Edition Source Code"). 8 9 Doom 3 BFG Edition Source Code is free software: you can redistribute it and/or modify 10 it under the terms of the GNU General Public License as published by 11 the Free Software Foundation, either version 3 of the License, or 12 (at your option) any later version. 13 14 Doom 3 BFG Edition Source Code is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 GNU General Public License for more details. 18 19 You should have received a copy of the GNU General Public License 20 along with Doom 3 BFG Edition Source Code. If not, see <http://www.gnu.org/licenses/>. 21 22 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. 23 24 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. 25 26 =========================================================================== 27 */ 28 #ifndef __LIGHTWEIGHT_COMPRESSION_H__ 29 #define __LIGHTWEIGHT_COMPRESSION_H__ 30 31 32 struct lzwCompressionData_t { 33 static const int LZW_DICT_BITS = 12; 34 static const int LZW_DICT_SIZE = 1 << LZW_DICT_BITS; 35 36 uint8 dictionaryK[LZW_DICT_SIZE]; 37 uint16 dictionaryW[LZW_DICT_SIZE]; 38 39 int nextCode; 40 int codeBits; 41 42 int codeWord; 43 44 uint64 tempValue; 45 int tempBits; 46 int bytesWritten; 47 }; 48 49 /* 50 ======================== 51 idLZWCompressor 52 Simple lzw based encoder/decoder 53 ======================== 54 */ 55 class idLZWCompressor { 56 public: 57 idLZWCompressor( lzwCompressionData_t * lzwData_ ) : lzwData( lzwData_ ) {} 58 59 static const int LZW_BLOCK_SIZE = ( 1 << 15 ); 60 static const int LZW_START_BITS = 9; 61 static const int LZW_FIRST_CODE = ( 1 << ( LZW_START_BITS - 1 ) ); 62 63 void Start( uint8 * data_, int maxSize, bool append = false ); 64 int ReadBits( int bits ); 65 int WriteChain( int code ); 66 void DecompressBlock(); 67 void WriteBits( uint32 value, int bits ); 68 int ReadByte( bool ignoreOverflow = false ); 69 void WriteByte( uint8 value ); 70 int Lookup( int w, int k ); 71 int AddToDict( int w, int k ); 72 bool BumpBits(); 73 int End(); 74 75 int Length() const { return lzwData->bytesWritten; } 76 int GetReadCount() const { return bytesRead; } 77 78 void Save(); 79 void Restore(); 80 81 bool IsOverflowed() { return overflowed; } 82 83 int Write( const void * data, int length ) { 84 uint8 * src = (uint8*)data; 85 86 for ( int i = 0; i < length && !IsOverflowed(); i++ ) { 87 WriteByte( src[i] ); 88 } 89 90 return length; 91 } 92 93 int Read( void * data, int length, bool ignoreOverflow = false ) { 94 uint8 * src = (uint8*)data; 95 96 for ( int i = 0; i < length; i++ ) { 97 int byte = ReadByte( ignoreOverflow ); 98 99 if ( byte == -1 ) { 100 return i; 101 } 102 103 src[i] = (uint8)byte; 104 } 105 106 return length; 107 } 108 109 int WriteR( const void * data, int length ) { 110 uint8 * src = (uint8*)data; 111 112 for ( int i = 0; i < length && !IsOverflowed(); i++ ) { 113 WriteByte( src[length - i - 1] ); 114 } 115 116 return length; 117 } 118 119 int ReadR( void * data, int length, bool ignoreOverflow = false ) { 120 uint8 * src = (uint8*)data; 121 122 for ( int i = 0; i < length; i++ ) { 123 int byte = ReadByte( ignoreOverflow ); 124 125 if ( byte == -1 ) { 126 return i; 127 } 128 129 src[length - i - 1] = (uint8)byte; 130 } 131 132 return length; 133 } 134 135 template<class type> ID_INLINE size_t WriteAgnostic( const type & c ) { 136 return Write( &c, sizeof( c ) ); 137 } 138 139 template<class type> ID_INLINE size_t ReadAgnostic( type & c, bool ignoreOverflow = false ) { 140 size_t r = Read( &c, sizeof( c ), ignoreOverflow ); 141 return r; 142 } 143 144 static const int DICTIONARY_HASH_BITS = 10; 145 static const int MAX_DICTIONARY_HASH = 1 << DICTIONARY_HASH_BITS; 146 static const int HASH_MASK = MAX_DICTIONARY_HASH - 1; 147 148 private: 149 void ClearHash(); 150 151 lzwCompressionData_t * lzwData; 152 uint16 hash[MAX_DICTIONARY_HASH]; 153 uint16 nextHash[lzwCompressionData_t::LZW_DICT_SIZE]; 154 155 // Used by DecompressBlock 156 int oldCode; 157 158 uint8 * data; // Read/write 159 int maxSize; 160 bool overflowed; 161 162 // For reading 163 int bytesRead; 164 uint8 block[LZW_BLOCK_SIZE]; 165 int blockSize; 166 int blockIndex; 167 168 // saving/restoring when overflow (when writing). 169 // Must call End directly after restoring (dictionary is bad so can't keep writing) 170 int savedBytesWritten; 171 int savedCodeWord; 172 int saveCodeBits; 173 uint64 savedTempValue; 174 int savedTempBits; 175 }; 176 177 /* 178 ======================== 179 idZeroRunLengthCompressor 180 Simple zero based run length encoder/decoder 181 ======================== 182 */ 183 class idZeroRunLengthCompressor { 184 public: 185 idZeroRunLengthCompressor() : zeroCount( 0 ), destStart( NULL ) { 186 } 187 188 void Start( uint8 * dest_, idLZWCompressor * comp_, int maxSize_ ); 189 bool WriteRun(); 190 bool WriteByte( uint8 value ); 191 byte ReadByte(); 192 void ReadBytes( byte * dest, int count ); 193 void WriteBytes( uint8 * src, int count ); 194 int End(); 195 196 int CompressedSize() const { return compressed; } 197 198 private: 199 int ReadInternal(); 200 201 int zeroCount; // Number of pending zeroes 202 idLZWCompressor * comp; 203 uint8 * destStart; 204 uint8 * dest; 205 int compressed; // Compressed size 206 int maxSize; 207 }; 208 209 #endif // __LIGHTWEIGHT_COMPRESSION_H__