2 ===========================================================================
5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
9 Doom 3 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.
14 Doom 3 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.
19 You should have received a copy of the GNU General Public License
20 along with Doom 3 Source Code. If not, see <http://www.gnu.org/licenses/>.
22 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.
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.
26 ===========================================================================
28 #include "../idlib/precompiled.h"
33 =================================================================================
37 =================================================================================
40 class idCompressor_None : public idCompressor {
42 idCompressor_None( void );
44 void Init( idFile *f, bool compress, int wordLength );
45 void FinishCompress( void );
46 float GetCompressionRatio( void ) const;
48 const char * GetName( void );
49 const char * GetFullPath( void );
50 int Read( void *outData, int outLength );
51 int Write( const void *inData, int inLength );
53 ID_TIME_T Timestamp( void );
55 void ForceFlush( void );
57 int Seek( long offset, fsOrigin_t origin );
66 idCompressor_None::idCompressor_None
69 idCompressor_None::idCompressor_None( void ) {
76 idCompressor_None::Init
79 void idCompressor_None::Init( idFile *f, bool compress, int wordLength ) {
81 this->compress = compress;
86 idCompressor_None::FinishCompress
89 void idCompressor_None::FinishCompress( void ) {
94 idCompressor_None::GetCompressionRatio
97 float idCompressor_None::GetCompressionRatio( void ) const {
103 idCompressor_None::GetName
106 const char *idCompressor_None::GetName( void ) {
108 return file->GetName();
116 idCompressor_None::GetFullPath
119 const char *idCompressor_None::GetFullPath( void ) {
121 return file->GetFullPath();
129 idCompressor_None::Write
132 int idCompressor_None::Write( const void *inData, int inLength ) {
133 if ( compress == false || inLength <= 0 ) {
136 return file->Write( inData, inLength );
141 idCompressor_None::Read
144 int idCompressor_None::Read( void *outData, int outLength ) {
145 if ( compress == true || outLength <= 0 ) {
148 return file->Read( outData, outLength );
153 idCompressor_None::Length
156 int idCompressor_None::Length( void ) {
158 return file->Length();
166 idCompressor_None::Timestamp
169 ID_TIME_T idCompressor_None::Timestamp( void ) {
171 return file->Timestamp();
179 idCompressor_None::Tell
182 int idCompressor_None::Tell( void ) {
192 idCompressor_None::ForceFlush
195 void idCompressor_None::ForceFlush( void ) {
203 idCompressor_None::Flush
206 void idCompressor_None::Flush( void ) {
214 idCompressor_None::Seek
217 int idCompressor_None::Seek( long offset, fsOrigin_t origin ) {
218 common->Error( "cannot seek on idCompressor" );
224 =================================================================================
226 idCompressor_BitStream
228 Base class for bit stream compression.
230 =================================================================================
233 class idCompressor_BitStream : public idCompressor_None {
235 idCompressor_BitStream( void ) {}
237 void Init( idFile *f, bool compress, int wordLength );
238 void FinishCompress( void );
239 float GetCompressionRatio( void ) const;
241 int Write( const void *inData, int inLength );
242 int Read( void *outData, int outLength );
252 const byte * readData;
261 void InitCompress( const void *inData, const int inLength );
262 void InitDecompress( void *outData, int outLength );
263 void WriteBits( int value, int numBits );
264 int ReadBits( int numBits );
265 void UnreadBits( int numBits );
266 int Compare( const byte *src1, int bitPtr1, const byte *src2, int bitPtr2, int maxBits ) const;
271 idCompressor_BitStream::Init
274 void idCompressor_BitStream::Init( idFile *f, bool compress, int wordLength ) {
276 assert( wordLength >= 1 && wordLength <= 32 );
279 this->compress = compress;
280 this->wordLength = wordLength;
297 idCompressor_BitStream::InitCompress
300 ID_INLINE void idCompressor_BitStream::InitCompress( const void *inData, const int inLength ) {
302 readLength = inLength;
305 readData = (const byte *) inData;
307 if ( !writeLength ) {
308 writeLength = sizeof( buffer );
317 idCompressor_BitStream::InitDecompress
320 ID_INLINE void idCompressor_BitStream::InitDecompress( void *outData, int outLength ) {
323 readLength = file->Read( buffer, sizeof( buffer ) );
329 writeLength = outLength;
332 writeData = (byte *) outData;
337 idCompressor_BitStream::WriteBits
340 void idCompressor_BitStream::WriteBits( int value, int numBits ) {
343 // Short circuit for writing single bytes at a time
344 if ( writeBit == 0 && numBits == 8 && writeByte < writeLength ) {
347 writeData[writeByte - 1] = value;
353 if ( writeBit == 0 ) {
354 if ( writeByte >= writeLength ) {
355 if ( writeData == buffer ) {
356 file->Write( buffer, writeByte );
361 writeByte += ( put >> 3 ) + ( writeBit != 0 );
362 writeTotalBytes += ( put >> 3 ) + ( writeBit != 0 );
366 writeData[writeByte] = 0;
371 if ( put > numBits ) {
374 fraction = value & ( ( 1 << put ) - 1 );
375 writeData[writeByte - 1] |= fraction << writeBit;
378 writeBit = ( writeBit + put ) & 7;
384 idCompressor_BitStream::ReadBits
387 int idCompressor_BitStream::ReadBits( int numBits ) {
388 int value, valueBits, get, fraction;
393 // Short circuit for reading single bytes at a time
394 if ( readBit == 0 && numBits == 8 && readByte < readLength ) {
397 return readData[readByte - 1];
400 while ( valueBits < numBits ) {
401 if ( readBit == 0 ) {
402 if ( readByte >= readLength ) {
403 if ( readData == buffer ) {
404 readLength = file->Read( buffer, sizeof( buffer ) );
407 get = numBits - valueBits;
409 readByte += ( get >> 3 ) + ( readBit != 0 );
410 readTotalBytes += ( get >> 3 ) + ( readBit != 0 );
418 if ( get > (numBits - valueBits) ) {
419 get = (numBits - valueBits);
421 fraction = readData[readByte - 1];
422 fraction >>= readBit;
423 fraction &= ( 1 << get ) - 1;
424 value |= fraction << valueBits;
426 readBit = ( readBit + get ) & 7;
434 idCompressor_BitStream::UnreadBits
437 void idCompressor_BitStream::UnreadBits( int numBits ) {
438 readByte -= ( numBits >> 3 );
439 readTotalBytes -= ( numBits >> 3 );
440 if ( readBit == 0 ) {
441 readBit = 8 - ( numBits & 7 );
443 readBit -= numBits & 7;
444 if ( readBit <= 0 ) {
447 readBit = ( readBit + 8 ) & 7;
450 if ( readByte < 0 ) {
458 idCompressor_BitStream::Compare
461 int idCompressor_BitStream::Compare( const byte *src1, int bitPtr1, const byte *src2, int bitPtr2, int maxBits ) const {
464 // If the two bit pointers are aligned then we can use a faster comparison
465 if ( ( bitPtr1 & 7 ) == (bitPtr2 & 7 ) && maxBits > 16 ) {
466 const byte *p1 = &src1[bitPtr1 >> 3];
467 const byte *p2 = &src2[bitPtr2 >> 3];
471 int bitsRemain = maxBits;
473 // Compare the first couple bits (if any)
475 for ( i = (bitPtr1 & 7); i < 8; i++, bits++ ) {
476 if ( ( ( *p1 >> i ) ^ ( *p2 >> i ) ) & 1 ) {
485 int remain = bitsRemain >> 3;
487 // Compare the middle bytes as ints
488 while ( remain >= 4 && (*(const int *)p1 == *(const int *)p2) ) {
495 // Compare the remaining bytes
496 while ( remain > 0 && (*p1 == *p2) ) {
503 // Compare the last couple of bits (if any)
506 finalBits = ( bitsRemain & 7 );
508 for ( i = 0; i < finalBits; i++, bits++ ) {
509 if ( ( ( *p1 >> i ) ^ ( *p2 >> i ) ) & 1 ) {
514 assert(bits == maxBits);
517 for ( i = 0; i < maxBits; i++ ) {
518 if ( ( ( src1[bitPtr1 >> 3] >> ( bitPtr1 & 7 ) ) ^ ( src2[bitPtr2 >> 3] >> ( bitPtr2 & 7 ) ) ) & 1 ) {
530 idCompressor_BitStream::Write
533 int idCompressor_BitStream::Write( const void *inData, int inLength ) {
536 if ( compress == false || inLength <= 0 ) {
540 InitCompress( inData, inLength );
542 for ( i = 0; i < inLength; i++ ) {
543 WriteBits( ReadBits( 8 ), 8 );
550 idCompressor_BitStream::FinishCompress
553 void idCompressor_BitStream::FinishCompress( void ) {
554 if ( compress == false ) {
559 file->Write( buffer, writeByte );
568 idCompressor_BitStream::Read
571 int idCompressor_BitStream::Read( void *outData, int outLength ) {
574 if ( compress == true || outLength <= 0 ) {
578 InitDecompress( outData, outLength );
580 for ( i = 0; i < outLength && readLength >= 0; i++ ) {
581 WriteBits( ReadBits( 8 ), 8 );
588 idCompressor_BitStream::GetCompressionRatio
591 float idCompressor_BitStream::GetCompressionRatio( void ) const {
593 return ( readTotalBytes - writeTotalBytes ) * 100.0f / readTotalBytes;
595 return ( writeTotalBytes - readTotalBytes ) * 100.0f / writeTotalBytes;
601 =================================================================================
603 idCompressor_RunLength
605 The following algorithm implements run length compression with an arbitrary
608 =================================================================================
611 class idCompressor_RunLength : public idCompressor_BitStream {
613 idCompressor_RunLength( void ) {}
615 void Init( idFile *f, bool compress, int wordLength );
617 int Write( const void *inData, int inLength );
618 int Read( void *outData, int outLength );
626 idCompressor_RunLength::Init
629 void idCompressor_RunLength::Init( idFile *f, bool compress, int wordLength ) {
630 idCompressor_BitStream::Init( f, compress, wordLength );
631 runLengthCode = ( 1 << wordLength ) - 1;
636 idCompressor_RunLength::Write
639 int idCompressor_RunLength::Write( const void *inData, int inLength ) {
640 int bits, nextBits, count;
642 if ( compress == false || inLength <= 0 ) {
646 InitCompress( inData, inLength );
648 while( readByte <= readLength ) {
650 bits = ReadBits( wordLength );
651 for ( nextBits = ReadBits( wordLength ); nextBits == bits; nextBits = ReadBits( wordLength ) ) {
653 if ( count >= ( 1 << wordLength ) ) {
654 if ( count >= ( 1 << wordLength ) + 3 || bits == runLengthCode ) {
659 if ( nextBits != bits ) {
660 UnreadBits( wordLength );
662 if ( count > 3 || bits == runLengthCode ) {
663 WriteBits( runLengthCode, wordLength );
664 WriteBits( bits, wordLength );
665 if ( bits != runLengthCode ) {
668 WriteBits( count - 1, wordLength );
671 WriteBits( bits, wordLength );
681 idCompressor_RunLength::Read
684 int idCompressor_RunLength::Read( void *outData, int outLength ) {
687 if ( compress == true || outLength <= 0 ) {
691 InitDecompress( outData, outLength );
693 while( writeByte <= writeLength && readLength >= 0 ) {
694 bits = ReadBits( wordLength );
695 if ( bits == runLengthCode ) {
696 bits = ReadBits( wordLength );
697 count = ReadBits( wordLength ) + 1;
698 if ( bits != runLengthCode ) {
702 WriteBits( bits, wordLength );
705 WriteBits( bits, wordLength );
714 =================================================================================
716 idCompressor_RunLength_ZeroBased
718 The following algorithm implements run length compression with an arbitrary
719 word size for data with a lot of zero bits.
721 =================================================================================
724 class idCompressor_RunLength_ZeroBased : public idCompressor_BitStream {
726 idCompressor_RunLength_ZeroBased( void ) {}
728 int Write( const void *inData, int inLength );
729 int Read( void *outData, int outLength );
736 idCompressor_RunLength_ZeroBased::Write
739 int idCompressor_RunLength_ZeroBased::Write( const void *inData, int inLength ) {
742 if ( compress == false || inLength <= 0 ) {
746 InitCompress( inData, inLength );
748 while( readByte <= readLength ) {
750 for ( bits = ReadBits( wordLength ); bits == 0 && count < ( 1 << wordLength ); bits = ReadBits( wordLength ) ) {
754 WriteBits( 0, wordLength );
755 WriteBits( count - 1, wordLength );
756 UnreadBits( wordLength );
758 WriteBits( bits, wordLength );
767 idCompressor_RunLength_ZeroBased::Read
770 int idCompressor_RunLength_ZeroBased::Read( void *outData, int outLength ) {
773 if ( compress == true || outLength <= 0 ) {
777 InitDecompress( outData, outLength );
779 while( writeByte <= writeLength && readLength >= 0 ) {
780 bits = ReadBits( wordLength );
782 count = ReadBits( wordLength ) + 1;
783 while( count-- > 0 ) {
784 WriteBits( 0, wordLength );
787 WriteBits( bits, wordLength );
796 =================================================================================
800 The following algorithm is based on the adaptive Huffman algorithm described
801 in Sayood's Data Compression book. The ranks are not actually stored, but
802 implicitly defined by the location of a node within a doubly-linked list
804 =================================================================================
807 const int HMAX = 256; // Maximum symbol
808 const int NYT = HMAX; // NYT = Not Yet Transmitted
809 const int INTERNAL_NODE = HMAX + 1; // internal node
811 typedef struct nodetype {
812 struct nodetype *left, *right, *parent; // tree structure
813 struct nodetype *next, *prev; // doubly-linked list
814 struct nodetype **head; // highest ranked node in block
819 class idCompressor_Huffman : public idCompressor_None {
821 idCompressor_Huffman( void ) {}
823 void Init( idFile *f, bool compress, int wordLength );
824 void FinishCompress( void );
825 float GetCompressionRatio( void ) const;
827 int Write( const void *inData, int inLength );
828 int Read( void *outData, int outLength );
839 int unCompressedSize;
841 huffmanNode_t * tree;
842 huffmanNode_t * lhead;
843 huffmanNode_t * ltail;
844 huffmanNode_t * loc[HMAX+1];
845 huffmanNode_t **freelist;
847 huffmanNode_t nodeList[768];
848 huffmanNode_t * nodePtrs[768];
851 void AddRef( byte ch );
852 int Receive( huffmanNode_t *node, int *ch );
853 void Transmit( int ch, byte *fout );
854 void PutBit( int bit, byte *fout, int *offset );
855 int GetBit( byte *fout, int *offset );
857 void Add_bit( char bit, byte *fout );
859 huffmanNode_t **Get_ppnode();
860 void Free_ppnode( huffmanNode_t **ppnode );
861 void Swap( huffmanNode_t *node1, huffmanNode_t *node2 );
862 void Swaplist( huffmanNode_t *node1, huffmanNode_t *node2 );
863 void Increment( huffmanNode_t *node );
864 void Send( huffmanNode_t *node, huffmanNode_t *child, byte *fout );
869 idCompressor_Huffman::Init
872 void idCompressor_Huffman::Init( idFile *f, bool compress, int wordLength ) {
876 this->compress = compress;
883 unCompressedSize = 0;
888 for( i = 0; i < (HMAX+1); i++ ) {
893 for( i = 0; i < 768; i++ ) {
894 memset( &nodeList[i], 0, sizeof(huffmanNode_t) );
899 // Add the NYT (not yet transmitted) node into the tree/list
900 tree = lhead = loc[NYT] = &nodeList[blocNode++];
903 lhead->next = lhead->prev = NULL;
904 tree->parent = tree->left = tree->right = NULL;
907 // Initialize the tree & list with the NYT node
908 tree = lhead = ltail = loc[NYT] = &nodeList[blocNode++];
911 lhead->next = lhead->prev = NULL;
912 tree->parent = tree->left = tree->right = NULL;
918 idCompressor_Huffman::PutBit
921 void idCompressor_Huffman::PutBit( int bit, byte *fout, int *offset) {
923 if ( (bloc&7) == 0 ) {
926 fout[(bloc>>3)] |= bit << (bloc&7);
933 idCompressor_Huffman::GetBit
936 int idCompressor_Huffman::GetBit( byte *fin, int *offset) {
939 t = (fin[(bloc>>3)] >> (bloc&7)) & 0x1;
947 idCompressor_Huffman::Add_bit
949 Add a bit to the output file (buffered)
952 void idCompressor_Huffman::Add_bit( char bit, byte *fout ) {
953 if ( (bloc&7) == 0 ) {
956 fout[(bloc>>3)] |= bit << (bloc&7);
962 idCompressor_Huffman::Get_bit
964 Get one bit from the input file (buffered)
967 int idCompressor_Huffman::Get_bit() {
971 if ( whb != blocIn ) {
972 blocMax += file->Read( seq, sizeof( seq ) );
976 t = ( seq[wh] >> ( bloc & 7 ) ) & 0x1;
983 idCompressor_Huffman::Get_ppnode
986 huffmanNode_t **idCompressor_Huffman::Get_ppnode() {
987 huffmanNode_t **tppnode;
989 return &nodePtrs[blocPtrs++];
992 freelist = (huffmanNode_t **)*tppnode;
999 idCompressor_Huffman::Free_ppnode
1002 void idCompressor_Huffman::Free_ppnode( huffmanNode_t **ppnode ) {
1003 *ppnode = (huffmanNode_t *)freelist;
1009 idCompressor_Huffman::Swap
1011 Swap the location of the given two nodes in the tree.
1014 void idCompressor_Huffman::Swap( huffmanNode_t *node1, huffmanNode_t *node2 ) {
1015 huffmanNode_t *par1, *par2;
1017 par1 = node1->parent;
1018 par2 = node2->parent;
1021 if ( par1->left == node1 ) {
1024 par1->right = node2;
1031 if ( par2->left == node2 ) {
1034 par2->right = node1;
1040 node1->parent = par2;
1041 node2->parent = par1;
1046 idCompressor_Huffman::Swaplist
1048 Swap the given two nodes in the linked list (update ranks)
1051 void idCompressor_Huffman::Swaplist( huffmanNode_t *node1, huffmanNode_t *node2 ) {
1052 huffmanNode_t *par1;
1055 node1->next = node2->next;
1059 node1->prev = node2->prev;
1062 if ( node1->next == node1 ) {
1063 node1->next = node2;
1065 if ( node2->next == node2 ) {
1066 node2->next = node1;
1068 if ( node1->next ) {
1069 node1->next->prev = node1;
1071 if ( node2->next ) {
1072 node2->next->prev = node2;
1074 if ( node1->prev ) {
1075 node1->prev->next = node1;
1077 if ( node2->prev ) {
1078 node2->prev->next = node2;
1084 idCompressor_Huffman::Increment
1087 void idCompressor_Huffman::Increment( huffmanNode_t *node ) {
1088 huffmanNode_t *lnode;
1094 if ( node->next != NULL && node->next->weight == node->weight ) {
1095 lnode = *node->head;
1096 if ( lnode != node->parent ) {
1097 Swap( lnode, node );
1099 Swaplist( lnode, node );
1101 if ( node->prev && node->prev->weight == node->weight ) {
1102 *node->head = node->prev;
1105 Free_ppnode( node->head );
1108 if ( node->next && node->next->weight == node->weight ) {
1109 node->head = node->next->head;
1111 node->head = Get_ppnode();
1114 if ( node->parent ) {
1115 Increment( node->parent );
1116 if ( node->prev == node->parent ) {
1117 Swaplist( node, node->parent );
1118 if ( *node->head == node ) {
1119 *node->head = node->parent;
1127 idCompressor_Huffman::AddRef
1130 void idCompressor_Huffman::AddRef( byte ch ) {
1131 huffmanNode_t *tnode, *tnode2;
1132 if ( loc[ch] == NULL ) { /* if this is the first transmission of this node */
1133 tnode = &nodeList[blocNode++];
1134 tnode2 = &nodeList[blocNode++];
1136 tnode2->symbol = INTERNAL_NODE;
1138 tnode2->next = lhead->next;
1139 if ( lhead->next ) {
1140 lhead->next->prev = tnode2;
1141 if ( lhead->next->weight == 1 ) {
1142 tnode2->head = lhead->next->head;
1144 tnode2->head = Get_ppnode();
1145 *tnode2->head = tnode2;
1148 tnode2->head = Get_ppnode();
1149 *tnode2->head = tnode2;
1151 lhead->next = tnode2;
1152 tnode2->prev = lhead;
1156 tnode->next = lhead->next;
1157 if ( lhead->next ) {
1158 lhead->next->prev = tnode;
1159 if ( lhead->next->weight == 1 ) {
1160 tnode->head = lhead->next->head;
1162 /* this should never happen */
1163 tnode->head = Get_ppnode();
1164 *tnode->head = tnode2;
1167 /* this should never happen */
1168 tnode->head = Get_ppnode();
1169 *tnode->head = tnode;
1171 lhead->next = tnode;
1172 tnode->prev = lhead;
1173 tnode->left = tnode->right = NULL;
1175 if ( lhead->parent ) {
1176 if ( lhead->parent->left == lhead ) { /* lhead is guaranteed to by the NYT */
1177 lhead->parent->left = tnode2;
1179 lhead->parent->right = tnode2;
1185 tnode2->right = tnode;
1186 tnode2->left = lhead;
1188 tnode2->parent = lhead->parent;
1189 lhead->parent = tnode->parent = tnode2;
1193 Increment( tnode2->parent );
1195 Increment( loc[ch] );
1201 idCompressor_Huffman::Receive
1206 int idCompressor_Huffman::Receive( huffmanNode_t *node, int *ch ) {
1207 while ( node && node->symbol == INTERNAL_NODE ) {
1217 return (*ch = node->symbol);
1222 idCompressor_Huffman::Send
1224 Send the prefix code for this node.
1227 void idCompressor_Huffman::Send( huffmanNode_t *node, huffmanNode_t *child, byte *fout ) {
1228 if ( node->parent ) {
1229 Send( node->parent, node, fout );
1232 if ( node->right == child ) {
1242 idCompressor_Huffman::Transmit
1247 void idCompressor_Huffman::Transmit( int ch, byte *fout ) {
1249 if ( loc[ch] == NULL ) {
1250 /* huffmanNode_t hasn't been transmitted, send a NYT, then the symbol */
1251 Transmit( NYT, fout );
1252 for ( i = 7; i >= 0; i-- ) {
1253 Add_bit( (char)((ch >> i) & 0x1), fout );
1256 Send( loc[ch], NULL, fout );
1262 idCompressor_Huffman::Write
1265 int idCompressor_Huffman::Write( const void *inData, int inLength ) {
1268 if ( compress == false || inLength <= 0 ) {
1272 for ( i = 0; i < inLength; i++ ) {
1273 ch = ((const byte *)inData)[i];
1274 Transmit( ch, seq ); /* Transmit symbol */
1275 AddRef( (byte)ch ); /* Do update */
1278 file->Write( seq, b );
1281 compressedSize += b;
1285 unCompressedSize += i;
1291 idCompressor_Huffman::FinishCompress
1294 void idCompressor_Huffman::FinishCompress( void ) {
1296 if ( compress == false ) {
1301 int str = (bloc>>3);
1303 file->Write( seq, str );
1304 compressedSize += str;
1310 idCompressor_Huffman::Read
1313 int idCompressor_Huffman::Read( void *outData, int outLength ) {
1316 if ( compress == true || outLength <= 0 ) {
1321 blocMax = file->Read( seq, sizeof( seq ) );
1325 for ( i = 0; i < outLength; i++ ) {
1327 // don't overflow reading from the file
1328 if ( ( bloc >> 3 ) > blocMax ) {
1331 Receive( tree, &ch ); /* Get a character */
1332 if ( ch == NYT ) { /* We got a NYT, get the symbol associated with it */
1334 for ( j = 0; j < 8; j++ ) {
1335 ch = ( ch << 1 ) + Get_bit();
1339 ((byte *)outData)[i] = ch; /* Write symbol */
1340 AddRef( (byte) ch ); /* Increment node */
1343 compressedSize = bloc >> 3;
1344 unCompressedSize += i;
1350 idCompressor_Huffman::GetCompressionRatio
1353 float idCompressor_Huffman::GetCompressionRatio( void ) const {
1354 return ( unCompressedSize - compressedSize ) * 100.0f / unCompressedSize;
1359 =================================================================================
1361 idCompressor_Arithmetic
1363 The following algorithm is based on the Arithmetic Coding methods described
1364 by Mark Nelson. The probability table is implicitly stored.
1366 =================================================================================
1369 const int AC_WORD_LENGTH = 8;
1370 const int AC_NUM_BITS = 16;
1371 const int AC_MSB_SHIFT = 15;
1372 const int AC_MSB2_SHIFT = 14;
1373 const int AC_MSB_MASK = 0x8000;
1374 const int AC_MSB2_MASK = 0x4000;
1375 const int AC_HIGH_INIT = 0xffff;
1376 const int AC_LOW_INIT = 0x0000;
1378 class idCompressor_Arithmetic : public idCompressor_BitStream {
1380 idCompressor_Arithmetic( void ) {}
1382 void Init( idFile *f, bool compress, int wordLength );
1383 void FinishCompress( void );
1385 int Write( const void *inData, int inLength );
1386 int Read( void *outData, int outLength );
1389 typedef struct acProbs_s {
1394 typedef struct acSymbol_s {
1400 acProbs_t probabilities[1<<AC_WORD_LENGTH];
1406 unsigned short high;
1407 unsigned short code;
1408 unsigned int underflowBits;
1412 void InitProbabilities( void );
1413 void UpdateProbabilities( acSymbol_t* symbol );
1414 int ProbabilityForCount( unsigned int count );
1416 void CharToSymbol( byte c, acSymbol_t* symbol );
1417 void EncodeSymbol( acSymbol_t* symbol );
1419 int SymbolFromCount( unsigned int count, acSymbol_t* symbol );
1420 int GetCurrentCount( void );
1421 void RemoveSymbolFromStream( acSymbol_t* symbol );
1423 void PutBit( int bit );
1426 void WriteOverflowBits( void );
1431 idCompressor_Arithmetic::Init
1434 void idCompressor_Arithmetic::Init( idFile *f, bool compress, int wordLength ) {
1435 idCompressor_BitStream::Init( f, compress, wordLength );
1443 idCompressor_Arithmetic::InitProbabilities
1446 void idCompressor_Arithmetic::InitProbabilities( void ) {
1447 high = AC_HIGH_INIT;
1452 for( int i = 0; i < (1<<AC_WORD_LENGTH); i++ ) {
1453 probabilities[ i ].low = i;
1454 probabilities[ i ].high = i + 1;
1457 scale = (1<<AC_WORD_LENGTH);
1462 idCompressor_Arithmetic::UpdateProbabilities
1465 void idCompressor_Arithmetic::UpdateProbabilities( acSymbol_t* symbol ) {
1468 x = symbol->position;
1470 probabilities[ x ].high++;
1472 for( i = x + 1; i < (1<<AC_WORD_LENGTH); i++ ) {
1473 probabilities[ i ].low++;
1474 probabilities[ i ].high++;
1482 idCompressor_Arithmetic::GetCurrentCount
1485 int idCompressor_Arithmetic::GetCurrentCount( void ) {
1486 return (unsigned int) ( ( ( ( (long) code - low ) + 1 ) * scale - 1 ) / ( ( (long) high - low ) + 1 ) );
1491 idCompressor_Arithmetic::ProbabilityForCount
1494 int idCompressor_Arithmetic::ProbabilityForCount( unsigned int count ) {
1497 int len, mid, offset, res;
1499 len = (1<<AC_WORD_LENGTH);
1505 if ( count >= probabilities[offset+mid].high ) {
1510 else if ( count < probabilities[offset+mid].low ) {
1523 for( j = 0; j < (1<<AC_WORD_LENGTH); j++ ) {
1524 if ( count >= probabilities[ j ].low && count < probabilities[ j ].high ) {
1538 idCompressor_Arithmetic::SymbolFromCount
1541 int idCompressor_Arithmetic::SymbolFromCount( unsigned int count, acSymbol_t* symbol ) {
1542 int p = ProbabilityForCount( count );
1543 symbol->low = probabilities[ p ].low;
1544 symbol->high = probabilities[ p ].high;
1545 symbol->position = p;
1551 idCompressor_Arithmetic::RemoveSymbolFromStream
1554 void idCompressor_Arithmetic::RemoveSymbolFromStream( acSymbol_t* symbol ) {
1557 range = ( long )( high - low ) + 1;
1558 high = low + ( unsigned short )( ( range * symbol->high ) / scale - 1 );
1559 low = low + ( unsigned short )( ( range * symbol->low ) / scale );
1563 if ( ( high & AC_MSB_MASK ) == ( low & AC_MSB_MASK ) ) {
1565 } else if( ( low & AC_MSB2_MASK ) == AC_MSB2_MASK && ( high & AC_MSB2_MASK ) == 0 ) {
1566 code ^= AC_MSB2_MASK;
1567 low &= AC_MSB2_MASK - 1;
1568 high |= AC_MSB2_MASK;
1570 UpdateProbabilities( symbol );
1578 code |= ReadBits( 1 );
1584 idCompressor_Arithmetic::GetBit
1587 int idCompressor_Arithmetic::GetBit( void ) {
1590 if( symbolBit <= 0 ) {
1591 // read a new symbol out
1593 symbolBuffer = SymbolFromCount( GetCurrentCount(), &symbol );
1594 RemoveSymbolFromStream( &symbol );
1595 symbolBit = AC_WORD_LENGTH;
1598 getbit = ( symbolBuffer >> ( AC_WORD_LENGTH - symbolBit ) ) & 1;
1606 idCompressor_Arithmetic::EncodeSymbol
1609 void idCompressor_Arithmetic::EncodeSymbol( acSymbol_t* symbol ) {
1612 // rescale high and low for the new symbol.
1613 range = ( high - low ) + 1;
1614 high = low + ( unsigned short )(( range * symbol->high ) / scale - 1 );
1615 low = low + ( unsigned short )(( range * symbol->low ) / scale );
1618 if ( ( high & AC_MSB_MASK ) == ( low & AC_MSB_MASK ) ) {
1619 // the high digits of low and high have converged, and can be written to the stream
1620 WriteBits( high >> AC_MSB_SHIFT, 1 );
1622 while( underflowBits > 0 ) {
1624 WriteBits( ~high >> AC_MSB_SHIFT, 1 );
1628 } else if ( ( low & AC_MSB2_MASK ) && !( high & AC_MSB2_MASK ) ) {
1629 // underflow is in danger of happening, 2nd digits are converging but 1st digits don't match
1631 low &= AC_MSB2_MASK - 1;
1632 high |= AC_MSB2_MASK;
1634 UpdateProbabilities( symbol );
1646 idCompressor_Arithmetic::CharToSymbol
1649 void idCompressor_Arithmetic::CharToSymbol( byte c, acSymbol_t* symbol ) {
1650 symbol->low = probabilities[ c ].low;
1651 symbol->high = probabilities[ c ].high;
1652 symbol->position = c;
1657 idCompressor_Arithmetic::PutBit
1660 void idCompressor_Arithmetic::PutBit( int putbit ) {
1661 symbolBuffer |= ( putbit & 1 ) << symbolBit;
1664 if( symbolBit >= AC_WORD_LENGTH ) {
1667 CharToSymbol( symbolBuffer, &symbol );
1668 EncodeSymbol( &symbol );
1677 idCompressor_Arithmetic::WriteOverflowBits
1680 void idCompressor_Arithmetic::WriteOverflowBits( void ) {
1682 WriteBits( low >> AC_MSB2_SHIFT, 1 );
1685 while( underflowBits-- > 0 ) {
1686 WriteBits( ~low >> AC_MSB2_SHIFT, 1 );
1692 idCompressor_Arithmetic::Write
1695 int idCompressor_Arithmetic::Write( const void *inData, int inLength ) {
1698 if ( compress == false || inLength <= 0 ) {
1702 InitCompress( inData, inLength );
1704 for( i = 0; i < inLength; i++ ) {
1705 if ( ( readTotalBytes & ( ( 1 << 14 ) - 1 ) ) == 0 ) {
1706 if ( readTotalBytes ) {
1707 WriteOverflowBits();
1712 WriteBits( 255, 8 );
1714 InitProbabilities();
1716 for ( j = 0; j < 8; j++ ) {
1717 PutBit( ReadBits( 1 ) );
1726 idCompressor_Arithmetic::FinishCompress
1729 void idCompressor_Arithmetic::FinishCompress( void ) {
1730 if ( compress == false ) {
1734 WriteOverflowBits();
1736 idCompressor_BitStream::FinishCompress();
1741 idCompressor_Arithmetic::Read
1744 int idCompressor_Arithmetic::Read( void *outData, int outLength ) {
1747 if ( compress == true || outLength <= 0 ) {
1751 InitDecompress( outData, outLength );
1753 for( i = 0; i < outLength && readLength >= 0; i++ ) {
1754 if ( ( writeTotalBytes & ( ( 1 << 14 ) - 1 ) ) == 0 ) {
1755 if ( writeTotalBytes ) {
1759 while( ReadBits( 8 ) == 0 && readLength > 0 ) {
1762 InitProbabilities();
1763 for ( j = 0; j < AC_NUM_BITS; j++ ) {
1765 code |= ReadBits( 1 );
1768 for ( j = 0; j < 8; j++ ) {
1769 WriteBits( GetBit(), 1 );
1778 =================================================================================
1782 In 1977 Abraham Lempel and Jacob Ziv presented a dictionary based scheme for
1783 text compression called LZ77. For any new text LZ77 outputs an offset/length
1784 pair to previously seen text and the next new byte after the previously seen
1787 In 1982 James Storer and Thomas Szymanski presented a modification on the work
1788 of Lempel and Ziv called LZSS. LZ77 always outputs an offset/length pair, even
1789 if a match is only one byte long. An offset/length pair usually takes more than
1790 a single byte to store and the compression is not optimal for small match sizes.
1791 LZSS uses a bit flag which tells whether the following data is a literal (byte)
1792 or an offset/length pair.
1794 The following algorithm is an implementation of LZSS with arbitrary word size.
1796 =================================================================================
1799 const int LZSS_BLOCK_SIZE = 65535;
1800 const int LZSS_HASH_BITS = 10;
1801 const int LZSS_HASH_SIZE = ( 1 << LZSS_HASH_BITS );
1802 const int LZSS_HASH_MASK = ( 1 << LZSS_HASH_BITS ) - 1;
1803 const int LZSS_OFFSET_BITS = 11;
1804 const int LZSS_LENGTH_BITS = 5;
1806 class idCompressor_LZSS : public idCompressor_BitStream {
1808 idCompressor_LZSS( void ) {}
1810 void Init( idFile *f, bool compress, int wordLength );
1811 void FinishCompress( void );
1813 int Write( const void *inData, int inLength );
1814 int Read( void *outData, int outLength );
1821 byte block[LZSS_BLOCK_SIZE];
1825 int hashTable[LZSS_HASH_SIZE];
1826 int hashNext[LZSS_BLOCK_SIZE * 8];
1829 bool FindMatch( int startWord, int startValue, int &wordOffset, int &numWords );
1830 void AddToHash( int index, int hash );
1831 int GetWordFromBlock( int wordOffset ) const;
1832 virtual void CompressBlock( void );
1833 virtual void DecompressBlock( void );
1838 idCompressor_LZSS::Init
1841 void idCompressor_LZSS::Init( idFile *f, bool compress, int wordLength ) {
1842 idCompressor_BitStream::Init( f, compress, wordLength );
1844 offsetBits = LZSS_OFFSET_BITS;
1845 lengthBits = LZSS_LENGTH_BITS;
1847 minMatchWords = ( offsetBits + lengthBits + wordLength ) / wordLength;
1854 idCompressor_LZSS::FindMatch
1857 bool idCompressor_LZSS::FindMatch( int startWord, int startValue, int &wordOffset, int &numWords ) {
1858 int i, n, hash, bottom, maxBits;
1860 wordOffset = startWord;
1861 numWords = minMatchWords - 1;
1863 bottom = Max( 0, startWord - ( ( 1 << offsetBits ) - 1 ) );
1864 maxBits = ( blockSize << 3 ) - startWord * wordLength;
1866 hash = startValue & LZSS_HASH_MASK;
1867 for ( i = hashTable[hash]; i >= bottom; i = hashNext[i] ) {
1868 n = Compare( block, i * wordLength, block, startWord * wordLength, Min( maxBits, ( startWord - i ) * wordLength ) );
1869 if ( n > numWords * wordLength ) {
1870 numWords = n / wordLength;
1872 if ( numWords > ( ( 1 << lengthBits ) - 1 + minMatchWords ) - 1 ) {
1873 numWords = ( ( 1 << lengthBits ) - 1 + minMatchWords ) - 1;
1879 return ( numWords >= minMatchWords );
1884 idCompressor_LZSS::AddToHash
1887 void idCompressor_LZSS::AddToHash( int index, int hash ) {
1888 hashNext[index] = hashTable[hash];
1889 hashTable[hash] = index;
1894 idCompressor_LZSS::GetWordFromBlock
1897 int idCompressor_LZSS::GetWordFromBlock( int wordOffset ) const {
1898 int blockBit, blockByte, value, valueBits, get, fraction;
1900 blockBit = ( wordOffset * wordLength ) & 7;
1901 blockByte = ( wordOffset * wordLength ) >> 3;
1902 if ( blockBit != 0 ) {
1909 while ( valueBits < wordLength ) {
1910 if ( blockBit == 0 ) {
1911 if ( blockByte >= LZSS_BLOCK_SIZE ) {
1917 if ( get > (wordLength - valueBits) ) {
1918 get = (wordLength - valueBits);
1920 fraction = block[blockByte - 1];
1921 fraction >>= blockBit;
1922 fraction &= ( 1 << get ) - 1;
1923 value |= fraction << valueBits;
1925 blockBit = ( blockBit + get ) & 7;
1933 idCompressor_LZSS::CompressBlock
1936 void idCompressor_LZSS::CompressBlock( void ) {
1937 int i, startWord, startValue, wordOffset, numWords;
1939 InitCompress( block, blockSize );
1941 memset( hashTable, -1, sizeof( hashTable ) );
1942 memset( hashNext, -1, sizeof( hashNext ) );
1945 while( readByte < readLength ) {
1946 startValue = ReadBits( wordLength );
1947 if ( FindMatch( startWord, startValue, wordOffset, numWords ) ) {
1949 WriteBits( startWord - wordOffset, offsetBits );
1950 WriteBits( numWords - minMatchWords, lengthBits );
1951 UnreadBits( wordLength );
1952 for ( i = 0; i < numWords; i++ ) {
1953 startValue = ReadBits( wordLength );
1954 AddToHash( startWord, startValue & LZSS_HASH_MASK );
1959 WriteBits( startValue, wordLength );
1960 AddToHash( startWord, startValue & LZSS_HASH_MASK );
1970 idCompressor_LZSS::DecompressBlock
1973 void idCompressor_LZSS::DecompressBlock( void ) {
1974 int i, offset, startWord, numWords;
1976 InitDecompress( block, LZSS_BLOCK_SIZE );
1979 while( writeByte < writeLength && readLength >= 0 ) {
1980 if ( ReadBits( 1 ) ) {
1981 offset = startWord - ReadBits( offsetBits );
1982 numWords = ReadBits( lengthBits ) + minMatchWords;
1983 for ( i = 0; i < numWords; i++ ) {
1984 WriteBits( GetWordFromBlock( offset + i ), wordLength );
1988 WriteBits( ReadBits( wordLength ), wordLength );
1993 blockSize = Min( writeByte, LZSS_BLOCK_SIZE );
1998 idCompressor_LZSS::Write
2001 int idCompressor_LZSS::Write( const void *inData, int inLength ) {
2004 if ( compress == false || inLength <= 0 ) {
2008 for ( n = i = 0; i < inLength; i += n ) {
2009 n = LZSS_BLOCK_SIZE - blockSize;
2010 if ( inLength - i >= n ) {
2011 memcpy( block + blockSize, ((const byte *)inData) + i, n );
2012 blockSize = LZSS_BLOCK_SIZE;
2016 memcpy( block + blockSize, ((const byte *)inData) + i, inLength - i );
2027 idCompressor_LZSS::FinishCompress
2030 void idCompressor_LZSS::FinishCompress( void ) {
2031 if ( compress == false ) {
2037 idCompressor_BitStream::FinishCompress();
2042 idCompressor_LZSS::Read
2045 int idCompressor_LZSS::Read( void *outData, int outLength ) {
2048 if ( compress == true || outLength <= 0 ) {
2056 for ( n = i = 0; i < outLength; i += n ) {
2060 n = blockSize - blockIndex;
2061 if ( outLength - i >= n ) {
2062 memcpy( ((byte *)outData) + i, block + blockIndex, n );
2066 memcpy( ((byte *)outData) + i, block + blockIndex, outLength - i );
2076 =================================================================================
2078 idCompressor_LZSS_WordAligned
2080 Outputs word aligned compressed data.
2082 =================================================================================
2085 class idCompressor_LZSS_WordAligned : public idCompressor_LZSS {
2087 idCompressor_LZSS_WordAligned( void ) {}
2089 void Init( idFile *f, bool compress, int wordLength );
2091 virtual void CompressBlock( void );
2092 virtual void DecompressBlock( void );
2097 idCompressor_LZSS_WordAligned::Init
2100 void idCompressor_LZSS_WordAligned::Init( idFile *f, bool compress, int wordLength ) {
2101 idCompressor_LZSS::Init( f, compress, wordLength );
2103 offsetBits = 2 * wordLength;
2104 lengthBits = wordLength;
2106 minMatchWords = ( offsetBits + lengthBits + wordLength ) / wordLength;
2113 idCompressor_LZSS_WordAligned::CompressBlock
2116 void idCompressor_LZSS_WordAligned::CompressBlock( void ) {
2117 int i, startWord, startValue, wordOffset, numWords;
2119 InitCompress( block, blockSize );
2121 memset( hashTable, -1, sizeof( hashTable ) );
2122 memset( hashNext, -1, sizeof( hashNext ) );
2125 while( readByte < readLength ) {
2126 startValue = ReadBits( wordLength );
2127 if ( FindMatch( startWord, startValue, wordOffset, numWords ) ) {
2128 WriteBits( numWords - ( minMatchWords - 1 ), lengthBits );
2129 WriteBits( startWord - wordOffset, offsetBits );
2130 UnreadBits( wordLength );
2131 for ( i = 0; i < numWords; i++ ) {
2132 startValue = ReadBits( wordLength );
2133 AddToHash( startWord, startValue & LZSS_HASH_MASK );
2137 WriteBits( 0, lengthBits );
2138 WriteBits( startValue, wordLength );
2139 AddToHash( startWord, startValue & LZSS_HASH_MASK );
2149 idCompressor_LZSS_WordAligned::DecompressBlock
2152 void idCompressor_LZSS_WordAligned::DecompressBlock( void ) {
2153 int i, offset, startWord, numWords;
2155 InitDecompress( block, LZSS_BLOCK_SIZE );
2158 while( writeByte < writeLength && readLength >= 0 ) {
2159 numWords = ReadBits( lengthBits );
2161 numWords += ( minMatchWords - 1 );
2162 offset = startWord - ReadBits( offsetBits );
2163 for ( i = 0; i < numWords; i++ ) {
2164 WriteBits( GetWordFromBlock( offset + i ), wordLength );
2168 WriteBits( ReadBits( wordLength ), wordLength );
2173 blockSize = Min( writeByte, LZSS_BLOCK_SIZE );
2177 =================================================================================
2181 http://www.unisys.com/about__unisys/lzw
2182 http://www.dogma.net/markn/articles/lzw/lzw.htm
2183 http://www.cs.cf.ac.uk/Dave/Multimedia/node214.html
2184 http://www.cs.duke.edu/csed/curious/compression/lzw.html
2185 http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lzw.html
2187 This is the same compression scheme used by GIF with the exception that
2188 the EOI and clear codes are not explicitly stored. Instead EOI happens
2189 when the input stream runs dry and CC happens when the table gets to big.
2191 This is a derivation of LZ78, but the dictionary starts with all single
2192 character values so only code words are output. It is similar in theory
2193 to LZ77, but instead of using the previous X bytes as a lookup table, a table
2194 is built as the stream is read. The compressor and decompressor use the
2195 same formula, so the tables should be exactly alike. The only catch is the
2196 decompressor is always one step behind the compressor and may get a code not
2197 yet in the table. In this case, it is easy to determine what the next code
2198 is going to be (it will be the previous string plus the first byte of the
2201 The dictionary can be any size, but 12 bits seems to produce best results for
2202 most sample data. The code size is variable. It starts with the minimum
2203 number of bits required to store the dictionary and automatically increases
2204 as the dictionary gets bigger (it starts at 9 bits and grows to 10 bits when
2205 item 512 is added, 11 bits when 1024 is added, etc...) once the the dictionary
2206 is filled (4096 items for a 12 bit dictionary), the whole thing is cleared and
2207 the process starts over again.
2209 The compressor increases the bit size after it adds the item, while the
2210 decompressor does before it adds the item. The difference is subtle, but
2211 it's because decompressor being one step behind. Otherwise, the decompressor
2212 would read 512 with only 9 bits.
2214 If "Hello" is in the dictionary, then "Hell", "Hel", "He" and "H" will be too.
2215 We use this to our advantage by storing the index of the previous code, and
2216 the value of the last character. This means when we traverse through the
2217 dictionary, we get the characters in reverse.
2219 Dictionary entries 0-255 are always going to have the values 0-255
2221 =================================================================================
2224 class idCompressor_LZW : public idCompressor_BitStream {
2226 idCompressor_LZW( void ) {}
2228 void Init( idFile *f, bool compress, int wordLength );
2229 void FinishCompress( void );
2231 int Write( const void *inData, int inLength );
2232 int Read( void *outData, int outLength );
2235 int AddToDict( int w, int k );
2236 int Lookup( int w, int k );
2240 int WriteChain( int code );
2241 void DecompressBlock();
2243 static const int LZW_BLOCK_SIZE = 32767;
2244 static const int LZW_START_BITS = 9;
2245 static const int LZW_FIRST_CODE = (1 << (LZW_START_BITS-1));
2246 static const int LZW_DICT_BITS = 12;
2247 static const int LZW_DICT_SIZE = 1 << LZW_DICT_BITS;
2253 } dictionary[LZW_DICT_SIZE];
2260 byte block[LZW_BLOCK_SIZE];
2264 // Used by the compressor
2267 // Used by the decompressor
2273 idCompressor_LZW::Init
2276 void idCompressor_LZW::Init( idFile *f, bool compress, int wordLength ) {
2277 idCompressor_BitStream::Init( f, compress, wordLength );
2279 for ( int i=0; i<LZW_FIRST_CODE; i++ ) {
2280 dictionary[i].k = i;
2281 dictionary[i].w = -1;
2285 nextCode = LZW_FIRST_CODE;
2286 codeBits = LZW_START_BITS;
2297 idCompressor_LZW::Read
2300 int idCompressor_LZW::Read( void *outData, int outLength ) {
2303 if ( compress == true || outLength <= 0 ) {
2311 for ( n = i = 0; i < outLength; i += n ) {
2315 n = blockSize - blockIndex;
2316 if ( outLength - i >= n ) {
2317 memcpy( ((byte *)outData) + i, block + blockIndex, n );
2321 memcpy( ((byte *)outData) + i, block + blockIndex, outLength - i );
2332 idCompressor_LZW::Lookup
2335 int idCompressor_LZW::Lookup( int w, int k ) {
2341 for ( j = index.First( w ^ k ); j >= 0 ; j = index.Next( j ) ) {
2342 if ( dictionary[ j ].k == k && dictionary[ j ].w == w ) {
2353 idCompressor_LZW::AddToDict
2356 int idCompressor_LZW::AddToDict( int w, int k ) {
2357 dictionary[ nextCode ].k = k;
2358 dictionary[ nextCode ].w = w;
2359 index.Add( w ^ k, nextCode );
2365 idCompressor_LZW::BumpBits
2367 Possibly increments codeBits
2368 Returns true if the dictionary was cleared
2371 bool idCompressor_LZW::BumpBits() {
2372 if ( nextCode == ( 1 << codeBits ) ) {
2374 if ( codeBits > LZW_DICT_BITS ) {
2375 nextCode = LZW_FIRST_CODE;
2376 codeBits = LZW_START_BITS;
2386 idCompressor_LZW::FinishCompress
2389 void idCompressor_LZW::FinishCompress( void ) {
2390 WriteBits( w, codeBits );
2391 idCompressor_BitStream::FinishCompress();
2396 idCompressor_LZW::Write
2399 int idCompressor_LZW::Write( const void *inData, int inLength ) {
2402 InitCompress( inData, inLength );
2404 for ( i = 0; i < inLength; i++ ) {
2405 int k = ReadBits( 8 );
2407 int code = Lookup(w, k);
2411 WriteBits( w, codeBits );
2412 if ( !BumpBits() ) {
2425 idCompressor_LZW::WriteChain
2426 The chain is stored backwards, so we have to write it to a buffer then output the buffer in reverse
2429 int idCompressor_LZW::WriteChain( int code ) {
2430 byte chain[LZW_DICT_SIZE];
2434 assert( i < LZW_DICT_SIZE-1 && code >= 0 );
2435 chain[i++] = dictionary[code].k;
2436 code = dictionary[code].w;
2437 } while ( code >= 0 );
2438 firstChar = chain[--i];
2439 for ( ; i >= 0; i-- ) {
2440 WriteBits( chain[i], 8 );
2447 idCompressor_LZW::DecompressBlock
2450 void idCompressor_LZW::DecompressBlock() {
2451 int code, firstChar;
2453 InitDecompress( block, LZW_BLOCK_SIZE );
2455 while( writeByte < writeLength - LZW_DICT_SIZE && readLength > 0 ) {
2456 assert( codeBits <= LZW_DICT_BITS );
2458 code = ReadBits( codeBits );
2459 if ( readLength == 0 ) {
2463 if ( oldCode == -1 ) {
2464 assert( code < 256 );
2465 WriteBits( code, 8 );
2471 if ( code >= nextCode ) {
2472 assert( code == nextCode );
2473 firstChar = WriteChain( oldCode );
2474 WriteBits( firstChar, 8 );
2476 firstChar = WriteChain( code );
2478 AddToDict( oldCode, firstChar );
2486 blockSize = Min( writeByte, LZW_BLOCK_SIZE );
2490 =================================================================================
2494 =================================================================================
2499 idCompressor::AllocNoCompression
2502 idCompressor * idCompressor::AllocNoCompression( void ) {
2503 return new idCompressor_None();
2508 idCompressor::AllocBitStream
2511 idCompressor * idCompressor::AllocBitStream( void ) {
2512 return new idCompressor_BitStream();
2517 idCompressor::AllocRunLength
2520 idCompressor * idCompressor::AllocRunLength( void ) {
2521 return new idCompressor_RunLength();
2526 idCompressor::AllocRunLength_ZeroBased
2529 idCompressor * idCompressor::AllocRunLength_ZeroBased( void ) {
2530 return new idCompressor_RunLength_ZeroBased();
2535 idCompressor::AllocHuffman
2538 idCompressor * idCompressor::AllocHuffman( void ) {
2539 return new idCompressor_Huffman();
2544 idCompressor::AllocArithmetic
2547 idCompressor * idCompressor::AllocArithmetic( void ) {
2548 return new idCompressor_Arithmetic();
2553 idCompressor::AllocLZSS
2556 idCompressor * idCompressor::AllocLZSS( void ) {
2557 return new idCompressor_LZSS();
2562 idCompressor::AllocLZSS_WordAligned
2565 idCompressor * idCompressor::AllocLZSS_WordAligned( void ) {
2566 return new idCompressor_LZSS_WordAligned();
2571 idCompressor::AllocLZW
2574 idCompressor * idCompressor::AllocLZW( void ) {
2575 return new idCompressor_LZW();