neo/framework/Compressor.cpp

   1 /*
   2 ===========================================================================
   3
   4 Doom 3 GPL Source Code
   5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
   6
   7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
   8
   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.
  13
  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.
  18
  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/>.
  21
  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.
  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 #include "../idlib/precompiled.h"
  29 #pragma hdrstop
  30
  31
  32 /*
  33 =================================================================================
  34
  35         idCompressor_None
  36
  37 =================================================================================
  38 */
  39
  40 class idCompressor_None : public idCompressor {
  41 public:
  42                                         idCompressor_None( void );
  43
  44         void                    Init( idFile *f, bool compress, int wordLength );
  45         void                    FinishCompress( void );
  46         float                   GetCompressionRatio( void ) const;
  47
  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 );
  52         int                             Length( void );
  53         ID_TIME_T                       Timestamp( void );
  54         int                             Tell( void );
  55         void                    ForceFlush( void );
  56         void                    Flush( void );
  57         int                             Seek( long offset, fsOrigin_t origin );
  58
  59 protected:
  60         idFile *                file;
  61         bool                    compress;
  62 };
  63
  64 /*
  65 ================
  66 idCompressor_None::idCompressor_None
  67 ================
  68 */
  69 idCompressor_None::idCompressor_None( void ) {
  70         file = NULL;
  71         compress = true;
  72 }
  73
  74 /*
  75 ================
  76 idCompressor_None::Init
  77 ================
  78 */
  79 void idCompressor_None::Init( idFile *f, bool compress, int wordLength ) {
  80         this->file = f;
  81         this->compress = compress;
  82 }
  83
  84 /*
  85 ================
  86 idCompressor_None::FinishCompress
  87 ================
  88 */
  89 void idCompressor_None::FinishCompress( void ) {
  90 }
  91
  92 /*
  93 ================
  94 idCompressor_None::GetCompressionRatio
  95 ================
  96 */
  97 float idCompressor_None::GetCompressionRatio( void ) const {
  98         return 0.0f;
  99 }
 100
 101 /*
 102 ================
 103 idCompressor_None::GetName
 104 ================
 105 */
 106 const char *idCompressor_None::GetName( void ) {
 107         if ( file ) {
 108                 return file->GetName();
 109         } else {
 110                 return "";
 111         }
 112 }
 113
 114 /*
 115 ================
 116 idCompressor_None::GetFullPath
 117 ================
 118 */
 119 const char *idCompressor_None::GetFullPath( void ) {
 120         if ( file ) {
 121                 return file->GetFullPath();
 122         } else {
 123                 return "";
 124         }
 125 }
 126
 127 /*
 128 ================
 129 idCompressor_None::Write
 130 ================
 131 */
 132 int idCompressor_None::Write( const void *inData, int inLength ) {
 133         if ( compress == false || inLength <= 0 ) {
 134                 return 0;
 135         }
 136         return file->Write( inData, inLength );
 137 }
 138
 139 /*
 140 ================
 141 idCompressor_None::Read
 142 ================
 143 */
 144 int idCompressor_None::Read( void *outData, int outLength ) {
 145         if ( compress == true || outLength <= 0 ) {
 146                 return 0;
 147         }
 148         return file->Read( outData, outLength );
 149 }
 150
 151 /*
 152 ================
 153 idCompressor_None::Length
 154 ================
 155 */
 156 int idCompressor_None::Length( void ) {
 157         if ( file ) {
 158                 return file->Length();
 159         } else {
 160                 return 0;
 161         }
 162 }
 163
 164 /*
 165 ================
 166 idCompressor_None::Timestamp
 167 ================
 168 */
 169 ID_TIME_T idCompressor_None::Timestamp( void ) {
 170         if ( file ) {
 171                 return file->Timestamp();
 172         } else {
 173                 return 0;
 174         }
 175 }
 176
 177 /*
 178 ================
 179 idCompressor_None::Tell
 180 ================
 181 */
 182 int idCompressor_None::Tell( void ) {
 183         if ( file ) {
 184                 return file->Tell();
 185         } else {
 186                 return 0;
 187         }
 188 }
 189
 190 /*
 191 ================
 192 idCompressor_None::ForceFlush
 193 ================
 194 */
 195 void idCompressor_None::ForceFlush( void ) {
 196         if ( file ) {
 197                 file->ForceFlush();
 198         }
 199 }
 200
 201 /*
 202 ================
 203 idCompressor_None::Flush
 204 ================
 205 */
 206 void idCompressor_None::Flush( void ) {
 207         if ( file ) {
 208                 file->ForceFlush();
 209         }
 210 }
 211
 212 /*
 213 ================
 214 idCompressor_None::Seek
 215 ================
 216 */
 217 int idCompressor_None::Seek( long offset, fsOrigin_t origin ) {
 218         common->Error( "cannot seek on idCompressor" );
 219         return -1;
 220 }
 221
 222
 223 /*
 224 =================================================================================
 225
 226         idCompressor_BitStream
 227
 228         Base class for bit stream compression.
 229
 230 =================================================================================
 231 */
 232
 233 class idCompressor_BitStream : public idCompressor_None {
 234 public:
 235                                         idCompressor_BitStream( void ) {}
 236
 237         void                    Init( idFile *f, bool compress, int wordLength );
 238         void                    FinishCompress( void );
 239         float                   GetCompressionRatio( void ) const;
 240
 241         int                             Write( const void *inData, int inLength );
 242         int                             Read( void *outData, int outLength );
 243
 244 protected:
 245         byte                    buffer[65536];
 246         int                             wordLength;
 247
 248         int                             readTotalBytes;
 249         int                             readLength;
 250         int                             readByte;
 251         int                             readBit;
 252         const byte *    readData;
 253
 254         int                             writeTotalBytes;
 255         int                             writeLength;
 256         int                             writeByte;
 257         int                             writeBit;
 258         byte *                  writeData;
 259
 260 protected:
 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;
 267 };
 268
 269 /*
 270 ================
 271 idCompressor_BitStream::Init
 272 ================
 273 */
 274 void idCompressor_BitStream::Init( idFile *f, bool compress, int wordLength ) {
 275
 276         assert( wordLength >= 1 && wordLength <= 32 );
 277
 278         this->file = f;
 279         this->compress = compress;
 280         this->wordLength = wordLength;
 281
 282         readTotalBytes = 0;
 283         readLength = 0;
 284         readByte = 0;
 285         readBit = 0;
 286         readData = NULL;
 287
 288         writeTotalBytes = 0;
 289         writeLength = 0;
 290         writeByte = 0;
 291         writeBit = 0;
 292         writeData = NULL;
 293 }
 294
 295 /*
 296 ================
 297 idCompressor_BitStream::InitCompress
 298 ================
 299 */
 300 ID_INLINE void idCompressor_BitStream::InitCompress( const void *inData, const int inLength ) {
 301
 302         readLength = inLength;
 303         readByte = 0;
 304         readBit = 0;
 305         readData = (const byte *) inData;
 306
 307         if ( !writeLength ) {
 308                 writeLength = sizeof( buffer );
 309                 writeByte = 0;
 310                 writeBit = 0;
 311                 writeData = buffer;
 312         }
 313 }
 314
 315 /*
 316 ================
 317 idCompressor_BitStream::InitDecompress
 318 ================
 319 */
 320 ID_INLINE void idCompressor_BitStream::InitDecompress( void *outData, int outLength ) {
 321
 322         if ( !readLength ) {
 323                 readLength = file->Read( buffer, sizeof( buffer ) );
 324                 readByte = 0;
 325                 readBit = 0;
 326                 readData = buffer;
 327         }
 328
 329         writeLength = outLength;
 330         writeByte = 0;
 331         writeBit = 0;
 332         writeData = (byte *) outData;
 333 }
 334
 335 /*
 336 ================
 337 idCompressor_BitStream::WriteBits
 338 ================
 339 */
 340 void idCompressor_BitStream::WriteBits( int value, int numBits ) {
 341         int put, fraction;
 342
 343         // Short circuit for writing single bytes at a time
 344         if ( writeBit == 0 && numBits == 8 && writeByte < writeLength ) {
 345                 writeByte++;
 346                 writeTotalBytes++;
 347                 writeData[writeByte - 1] = value;
 348                 return;
 349         }
 350
 351
 352         while( numBits ) {
 353                 if ( writeBit == 0 ) {
 354                         if ( writeByte >= writeLength ) {
 355                                 if ( writeData == buffer ) {
 356                                         file->Write( buffer, writeByte );
 357                                         writeByte = 0;
 358                                 } else {
 359                                         put = numBits;
 360                                         writeBit = put & 7;
 361                                         writeByte += ( put >> 3 ) + ( writeBit != 0 );
 362                                         writeTotalBytes += ( put >> 3 ) + ( writeBit != 0 );
 363                                         return;
 364                                 }
 365                         }
 366                         writeData[writeByte] = 0;
 367                         writeByte++;
 368                         writeTotalBytes++;
 369                 }
 370                 put = 8 - writeBit;
 371                 if ( put > numBits ) {
 372                         put = numBits;
 373                 }
 374                 fraction = value & ( ( 1 << put ) - 1 );
 375                 writeData[writeByte - 1] |= fraction << writeBit;
 376                 numBits -= put;
 377                 value >>= put;
 378                 writeBit = ( writeBit + put ) & 7;
 379         }
 380 }
 381
 382 /*
 383 ================
 384 idCompressor_BitStream::ReadBits
 385 ================
 386 */
 387 int idCompressor_BitStream::ReadBits( int numBits ) {
 388         int value, valueBits, get, fraction;
 389
 390         value = 0;
 391         valueBits = 0;
 392
 393         // Short circuit for reading single bytes at a time
 394         if ( readBit == 0 && numBits == 8 && readByte < readLength ) {
 395                 readByte++;
 396                 readTotalBytes++;
 397                 return readData[readByte - 1];
 398         }
 399
 400         while ( valueBits < numBits ) {
 401                 if ( readBit == 0 ) {
 402                         if ( readByte >= readLength ) {
 403                                 if ( readData == buffer ) {
 404                                         readLength = file->Read( buffer, sizeof( buffer ) );
 405                                         readByte = 0;
 406                                 } else {
 407                                         get = numBits - valueBits;
 408                                         readBit = get & 7;
 409                                         readByte += ( get >> 3 ) + ( readBit != 0 );
 410                                         readTotalBytes += ( get >> 3 ) + ( readBit != 0 );
 411                                         return value;
 412                                 }
 413                         }
 414                         readByte++;
 415                         readTotalBytes++;
 416                 }
 417                 get = 8 - readBit;
 418                 if ( get > (numBits - valueBits) ) {
 419                         get = (numBits - valueBits);
 420                 }
 421                 fraction = readData[readByte - 1];
 422                 fraction >>= readBit;
 423                 fraction &= ( 1 << get ) - 1;
 424                 value |= fraction << valueBits;
 425                 valueBits += get;
 426                 readBit = ( readBit + get ) & 7;
 427         }
 428
 429         return value;
 430 }
 431
 432 /*
 433 ================
 434 idCompressor_BitStream::UnreadBits
 435 ================
 436 */
 437 void idCompressor_BitStream::UnreadBits( int numBits ) {
 438         readByte -= ( numBits >> 3 );
 439         readTotalBytes -= ( numBits >> 3 );
 440         if ( readBit == 0 ) {
 441                 readBit = 8 - ( numBits & 7 );
 442         } else {
 443                 readBit -= numBits & 7;
 444                 if ( readBit <= 0 ) {
 445                         readByte--;
 446                         readTotalBytes--;
 447                         readBit = ( readBit + 8 ) & 7;
 448                 }
 449         }
 450         if ( readByte < 0 ) {
 451                 readByte = 0;
 452                 readBit = 0;
 453         }
 454 }
 455
 456 /*
 457 ================
 458 idCompressor_BitStream::Compare
 459 ================
 460 */
 461 int idCompressor_BitStream::Compare( const byte *src1, int bitPtr1, const byte *src2, int bitPtr2, int maxBits ) const {
 462         int i;
 463
 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];
 468
 469                 int bits = 0;
 470
 471                 int bitsRemain = maxBits;
 472
 473                 // Compare the first couple bits (if any)
 474                 if ( bitPtr1 & 7 ) {
 475                         for ( i = (bitPtr1 & 7); i < 8; i++, bits++ ) {
 476                                 if ( ( ( *p1 >> i ) ^ ( *p2 >> i ) ) & 1 ) {
 477                                         return bits;
 478                                 }
 479                                 bitsRemain--;
 480                         }
 481                         p1++;
 482                         p2++;
 483                 }
 484
 485                 int remain = bitsRemain >> 3;
 486
 487                 // Compare the middle bytes as ints
 488                 while ( remain >= 4 && (*(const int *)p1 == *(const int *)p2) ) {
 489                         p1 += 4;
 490                         p2 += 4;
 491                         remain -= 4;
 492                         bits += 32;
 493                 }
 494
 495                 // Compare the remaining bytes
 496                 while ( remain > 0 && (*p1 == *p2) ) {
 497                         p1++;
 498                         p2++;
 499                         remain--;
 500                         bits += 8;
 501                 }
 502
 503                 // Compare the last couple of bits (if any)
 504                 int finalBits = 8;
 505                 if ( remain == 0 ) {
 506                         finalBits = ( bitsRemain & 7 );
 507                 }
 508                 for ( i = 0; i < finalBits; i++, bits++ ) {
 509                         if ( ( ( *p1 >> i ) ^ ( *p2 >> i ) ) & 1 ) {
 510                                 return bits;
 511                         }
 512                 }
 513
 514                 assert(bits == maxBits);
 515                 return bits;
 516         } else {
 517         for ( i = 0; i < maxBits; i++ ) {
 518                         if ( ( ( src1[bitPtr1 >> 3] >> ( bitPtr1 & 7 ) ) ^ ( src2[bitPtr2 >> 3] >> ( bitPtr2 & 7 ) ) ) & 1 ) {
 519                         break;
 520                 }
 521                 bitPtr1++;
 522                 bitPtr2++;
 523         }
 524         return i;
 525 }
 526 }
 527
 528 /*
 529 ================
 530 idCompressor_BitStream::Write
 531 ================
 532 */
 533 int idCompressor_BitStream::Write( const void *inData, int inLength ) {
 534         int i;
 535
 536         if ( compress == false || inLength <= 0 ) {
 537                 return 0;
 538         }
 539
 540         InitCompress( inData, inLength );
 541
 542         for ( i = 0; i < inLength; i++ ) {
 543                 WriteBits( ReadBits( 8 ), 8 );
 544         }
 545         return i;
 546 }
 547
 548 /*
 549 ================
 550 idCompressor_BitStream::FinishCompress
 551 ================
 552 */
 553 void idCompressor_BitStream::FinishCompress( void ) {
 554         if ( compress == false ) {
 555                 return;
 556         }
 557
 558         if ( writeByte ) {
 559                 file->Write( buffer, writeByte );
 560         }
 561         writeLength = 0;
 562         writeByte = 0;
 563         writeBit = 0;
 564 }
 565
 566 /*
 567 ================
 568 idCompressor_BitStream::Read
 569 ================
 570 */
 571 int idCompressor_BitStream::Read( void *outData, int outLength ) {
 572         int i;
 573
 574         if ( compress == true || outLength <= 0 ) {
 575                 return 0;
 576         }
 577
 578         InitDecompress( outData, outLength );
 579
 580         for ( i = 0; i < outLength && readLength >= 0; i++ ) {
 581                 WriteBits( ReadBits( 8 ), 8 );
 582         }
 583         return i;
 584 }
 585
 586 /*
 587 ================
 588 idCompressor_BitStream::GetCompressionRatio
 589 ================
 590 */
 591 float idCompressor_BitStream::GetCompressionRatio( void ) const {
 592         if ( compress ) {
 593                 return ( readTotalBytes - writeTotalBytes ) * 100.0f / readTotalBytes;
 594         } else {
 595                 return ( writeTotalBytes - readTotalBytes ) * 100.0f / writeTotalBytes;
 596         }
 597 }
 598
 599
 600 /*
 601 =================================================================================
 602
 603         idCompressor_RunLength
 604
 605         The following algorithm implements run length compression with an arbitrary
 606         word size.
 607
 608 =================================================================================
 609 */
 610
 611 class idCompressor_RunLength : public idCompressor_BitStream {
 612 public:
 613                                         idCompressor_RunLength( void ) {}
 614
 615         void                    Init( idFile *f, bool compress, int wordLength );
 616
 617         int                             Write( const void *inData, int inLength );
 618         int                             Read( void *outData, int outLength );
 619
 620 private:
 621         int                             runLengthCode;
 622 };
 623
 624 /*
 625 ================
 626 idCompressor_RunLength::Init
 627 ================
 628 */
 629 void idCompressor_RunLength::Init( idFile *f, bool compress, int wordLength ) {
 630         idCompressor_BitStream::Init( f, compress, wordLength );
 631         runLengthCode = ( 1 << wordLength ) - 1;
 632 }
 633
 634 /*
 635 ================
 636 idCompressor_RunLength::Write
 637 ================
 638 */
 639 int idCompressor_RunLength::Write( const void *inData, int inLength ) {
 640         int bits, nextBits, count;
 641
 642         if ( compress == false || inLength <= 0 ) {
 643                 return 0;
 644         }
 645
 646         InitCompress( inData, inLength );
 647
 648         while( readByte <= readLength ) {
 649                 count = 1;
 650                 bits = ReadBits( wordLength );
 651                 for ( nextBits = ReadBits( wordLength ); nextBits == bits; nextBits = ReadBits( wordLength ) ) {
 652                         count++;
 653                         if ( count >= ( 1 << wordLength ) ) {
 654                                 if ( count >= ( 1 << wordLength ) + 3 || bits == runLengthCode ) {
 655                                         break;
 656                                 }
 657                         }
 658                 }
 659                 if ( nextBits != bits ) {
 660                         UnreadBits( wordLength );
 661                 }
 662                 if ( count > 3 || bits == runLengthCode ) {
 663                         WriteBits( runLengthCode, wordLength );
 664                         WriteBits( bits, wordLength );
 665                         if ( bits != runLengthCode ) {
 666                                 count -= 3;
 667                         }
 668                         WriteBits( count - 1, wordLength );
 669                 } else {
 670                         while( count-- ) {
 671                                 WriteBits( bits, wordLength );
 672                         }
 673                 }
 674         }
 675
 676         return inLength;
 677 }
 678
 679 /*
 680 ================
 681 idCompressor_RunLength::Read
 682 ================
 683 */
 684 int idCompressor_RunLength::Read( void *outData, int outLength ) {
 685         int bits, count;
 686
 687         if ( compress == true || outLength <= 0 ) {
 688                 return 0;
 689         }
 690
 691         InitDecompress( outData, outLength );
 692
 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 ) {
 699                                 count += 3;
 700                         }
 701                         while( count-- ) {
 702                                 WriteBits( bits, wordLength );
 703                         }
 704                 } else {
 705                         WriteBits( bits, wordLength );
 706                 }
 707         }
 708
 709         return writeByte;
 710 }
 711
 712
 713 /*
 714 =================================================================================
 715
 716         idCompressor_RunLength_ZeroBased
 717
 718         The following algorithm implements run length compression with an arbitrary
 719         word size for data with a lot of zero bits.
 720
 721 =================================================================================
 722 */
 723
 724 class idCompressor_RunLength_ZeroBased : public idCompressor_BitStream {
 725 public:
 726                                         idCompressor_RunLength_ZeroBased( void ) {}
 727
 728         int                             Write( const void *inData, int inLength );
 729         int                             Read( void *outData, int outLength );
 730
 731 private:
 732 };
 733
 734 /*
 735 ================
 736 idCompressor_RunLength_ZeroBased::Write
 737 ================
 738 */
 739 int idCompressor_RunLength_ZeroBased::Write( const void *inData, int inLength ) {
 740         int bits, count;
 741
 742         if ( compress == false || inLength <= 0 ) {
 743                 return 0;
 744         }
 745
 746         InitCompress( inData, inLength );
 747
 748         while( readByte <= readLength ) {
 749                 count = 0;
 750                 for ( bits = ReadBits( wordLength ); bits == 0 && count < ( 1 << wordLength ); bits = ReadBits( wordLength ) ) {
 751                         count++;
 752                 }
 753                 if ( count ) {
 754                         WriteBits( 0, wordLength );
 755                         WriteBits( count - 1, wordLength );
 756                         UnreadBits( wordLength );
 757                 } else {
 758                         WriteBits( bits, wordLength );
 759                 }
 760         }
 761
 762         return inLength;
 763 }
 764
 765 /*
 766 ================
 767 idCompressor_RunLength_ZeroBased::Read
 768 ================
 769 */
 770 int idCompressor_RunLength_ZeroBased::Read( void *outData, int outLength ) {
 771         int bits, count;
 772
 773         if ( compress == true || outLength <= 0 ) {
 774                 return 0;
 775         }
 776
 777         InitDecompress( outData, outLength );
 778
 779         while( writeByte <= writeLength && readLength >= 0 ) {
 780                 bits = ReadBits( wordLength );
 781                 if ( bits == 0 ) {
 782                         count = ReadBits( wordLength ) + 1;
 783                         while( count-- > 0 ) {
 784                                 WriteBits( 0, wordLength );
 785                         }
 786                 } else {
 787                         WriteBits( bits, wordLength );
 788                 }
 789         }
 790
 791         return writeByte;
 792 }
 793
 794
 795 /*
 796 =================================================================================
 797
 798         idCompressor_Huffman
 799
 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
 803
 804 =================================================================================
 805 */
 806
 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
 810
 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
 815         int                             weight;
 816         int                             symbol;
 817 } huffmanNode_t;
 818
 819 class idCompressor_Huffman : public idCompressor_None {
 820 public:
 821                                         idCompressor_Huffman( void ) {}
 822
 823         void                    Init( idFile *f, bool compress, int wordLength );
 824         void                    FinishCompress( void );
 825         float                   GetCompressionRatio( void ) const;
 826
 827         int                             Write( const void *inData, int inLength );
 828         int                             Read( void *outData, int outLength );
 829
 830 private:
 831         byte                    seq[65536];
 832         int                             bloc;
 833         int                             blocMax;
 834         int                             blocIn;
 835         int                             blocNode;
 836         int                             blocPtrs;
 837
 838         int                             compressedSize;
 839         int                             unCompressedSize;
 840
 841         huffmanNode_t * tree;
 842         huffmanNode_t * lhead;
 843         huffmanNode_t * ltail;
 844         huffmanNode_t * loc[HMAX+1];
 845         huffmanNode_t **freelist;
 846
 847         huffmanNode_t   nodeList[768];
 848         huffmanNode_t * nodePtrs[768];
 849
 850 private:
 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 );
 856
 857         void                    Add_bit( char bit, byte *fout );
 858         int                             Get_bit();
 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 );
 865 };
 866
 867 /*
 868 ================
 869 idCompressor_Huffman::Init
 870 ================
 871 */
 872 void idCompressor_Huffman::Init( idFile *f, bool compress, int wordLength ) {
 873         int i;
 874
 875         this->file = f;
 876         this->compress = compress;
 877         bloc = 0;
 878         blocMax = 0;
 879         blocIn = 0;
 880         blocNode = 0;
 881         blocPtrs = 0;
 882         compressedSize = 0;
 883         unCompressedSize = 0;
 884
 885         tree = NULL;
 886         lhead = NULL;
 887         ltail = NULL;
 888         for( i = 0; i < (HMAX+1); i++ ) {
 889                 loc[i] = NULL;
 890         }
 891         freelist = NULL;
 892
 893         for( i = 0; i < 768; i++ ) {
 894                 memset( &nodeList[i], 0, sizeof(huffmanNode_t) );
 895                 nodePtrs[i] = NULL;
 896         }
 897
 898         if ( compress ) {
 899                 // Add the NYT (not yet transmitted) node into the tree/list
 900                 tree = lhead = loc[NYT] = &nodeList[blocNode++];
 901                 tree->symbol = NYT;
 902                 tree->weight = 0;
 903                 lhead->next = lhead->prev = NULL;
 904                 tree->parent = tree->left = tree->right = NULL;
 905                 loc[NYT] = tree;
 906         } else {
 907                 // Initialize the tree & list with the NYT node
 908                 tree = lhead = ltail = loc[NYT] = &nodeList[blocNode++];
 909                 tree->symbol = NYT;
 910                 tree->weight = 0;
 911                 lhead->next = lhead->prev = NULL;
 912                 tree->parent = tree->left = tree->right = NULL;
 913         }
 914 }
 915
 916 /*
 917 ================
 918 idCompressor_Huffman::PutBit
 919 ================
 920 */
 921 void idCompressor_Huffman::PutBit( int bit, byte *fout, int *offset) {
 922         bloc = *offset;
 923         if ( (bloc&7) == 0 ) {
 924                 fout[(bloc>>3)] = 0;
 925         }
 926         fout[(bloc>>3)] |= bit << (bloc&7);
 927         bloc++;
 928         *offset = bloc;
 929 }
 930
 931 /*
 932 ================
 933 idCompressor_Huffman::GetBit
 934 ================
 935 */
 936 int idCompressor_Huffman::GetBit( byte *fin, int *offset) {
 937         int t;
 938         bloc = *offset;
 939         t = (fin[(bloc>>3)] >> (bloc&7)) & 0x1;
 940         bloc++;
 941         *offset = bloc;
 942         return t;
 943 }
 944
 945 /*
 946 ================
 947 idCompressor_Huffman::Add_bit
 948
 949   Add a bit to the output file (buffered)
 950 ================
 951 */
 952 void idCompressor_Huffman::Add_bit( char bit, byte *fout ) {
 953         if ( (bloc&7) == 0 ) {
 954                 fout[(bloc>>3)] = 0;
 955         }
 956         fout[(bloc>>3)] |= bit << (bloc&7);
 957         bloc++;
 958 }
 959
 960 /*
 961 ================
 962 idCompressor_Huffman::Get_bit
 963
 964   Get one bit from the input file (buffered)
 965 ================
 966 */
 967 int idCompressor_Huffman::Get_bit() {
 968         int t;
 969         int wh = bloc >> 3;
 970         int whb = wh>> 16;
 971         if ( whb != blocIn ) {
 972                 blocMax += file->Read( seq, sizeof( seq ) );
 973                 blocIn++;
 974         }
 975         wh &= 0xffff;
 976         t = ( seq[wh] >> ( bloc & 7 ) ) & 0x1;
 977         bloc++;
 978         return t;
 979 }
 980
 981 /*
 982 ================
 983 idCompressor_Huffman::Get_ppnode
 984 ================
 985 */
 986 huffmanNode_t **idCompressor_Huffman::Get_ppnode() {
 987         huffmanNode_t **tppnode;
 988         if ( !freelist ) {
 989                 return &nodePtrs[blocPtrs++];
 990         } else {
 991                 tppnode = freelist;
 992                 freelist = (huffmanNode_t **)*tppnode;
 993                 return tppnode;
 994         }
 995 }
 996
 997 /*
 998 ================
 999 idCompressor_Huffman::Free_ppnode
1000 ================
1001 */
1002 void idCompressor_Huffman::Free_ppnode( huffmanNode_t **ppnode ) {
1003         *ppnode = (huffmanNode_t *)freelist;
1004         freelist = ppnode;
1005 }
1006
1007 /*
1008 ================
1009 idCompressor_Huffman::Swap
1010
1011   Swap the location of the given two nodes in the tree.
1012 ================
1013 */
1014 void idCompressor_Huffman::Swap( huffmanNode_t *node1, huffmanNode_t *node2 ) {
1015         huffmanNode_t *par1, *par2;
1016
1017         par1 = node1->parent;
1018         par2 = node2->parent;
1019
1020         if ( par1 ) {
1021                 if ( par1->left == node1 ) {
1022                         par1->left = node2;
1023                 } else {
1024               par1->right = node2;
1025                 }
1026         } else {
1027                 tree = node2;
1028         }
1029
1030         if ( par2 ) {
1031                 if ( par2->left == node2 ) {
1032                         par2->left = node1;
1033                 } else {
1034                         par2->right = node1;
1035                 }
1036         } else {
1037                 tree = node1;
1038         }
1039
1040         node1->parent = par2;
1041         node2->parent = par1;
1042 }
1043
1044 /*
1045 ================
1046 idCompressor_Huffman::Swaplist
1047
1048   Swap the given two nodes in the linked list (update ranks)
1049 ================
1050 */
1051 void idCompressor_Huffman::Swaplist( huffmanNode_t *node1, huffmanNode_t *node2 ) {
1052         huffmanNode_t *par1;
1053
1054         par1 = node1->next;
1055         node1->next = node2->next;
1056         node2->next = par1;
1057
1058         par1 = node1->prev;
1059         node1->prev = node2->prev;
1060         node2->prev = par1;
1061
1062         if ( node1->next == node1 ) {
1063                 node1->next = node2;
1064         }
1065         if ( node2->next == node2 ) {
1066                 node2->next = node1;
1067         }
1068         if ( node1->next ) {
1069                 node1->next->prev = node1;
1070         }
1071         if ( node2->next ) {
1072                 node2->next->prev = node2;
1073         }
1074         if ( node1->prev ) {
1075                 node1->prev->next = node1;
1076         }
1077         if ( node2->prev ) {
1078                 node2->prev->next = node2;
1079         }
1080 }
1081
1082 /*
1083 ================
1084 idCompressor_Huffman::Increment
1085 ================
1086 */
1087 void idCompressor_Huffman::Increment( huffmanNode_t *node ) {
1088         huffmanNode_t *lnode;
1089
1090         if ( !node ) {
1091                 return;
1092         }
1093
1094         if ( node->next != NULL && node->next->weight == node->weight ) {
1095             lnode = *node->head;
1096                 if ( lnode != node->parent ) {
1097                         Swap( lnode, node );
1098                 }
1099                 Swaplist( lnode, node );
1100         }
1101         if ( node->prev && node->prev->weight == node->weight ) {
1102                 *node->head = node->prev;
1103         } else {
1104             *node->head = NULL;
1105                 Free_ppnode( node->head );
1106         }
1107         node->weight++;
1108         if ( node->next && node->next->weight == node->weight ) {
1109                 node->head = node->next->head;
1110         } else {
1111                 node->head = Get_ppnode();
1112                 *node->head = node;
1113         }
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;
1120                         }
1121                 }
1122         }
1123 }
1124
1125 /*
1126 ================
1127 idCompressor_Huffman::AddRef
1128 ================
1129 */
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++];
1135
1136                 tnode2->symbol = INTERNAL_NODE;
1137                 tnode2->weight = 1;
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;
1143                         } else {
1144                                 tnode2->head = Get_ppnode();
1145                                 *tnode2->head = tnode2;
1146                         }
1147                 } else {
1148                         tnode2->head = Get_ppnode();
1149                         *tnode2->head = tnode2;
1150                 }
1151                 lhead->next = tnode2;
1152                 tnode2->prev = lhead;
1153
1154                 tnode->symbol = ch;
1155                 tnode->weight = 1;
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;
1161                         } else {
1162                                 /* this should never happen */
1163                                 tnode->head = Get_ppnode();
1164                                 *tnode->head = tnode2;
1165                     }
1166                 } else {
1167                         /* this should never happen */
1168                         tnode->head = Get_ppnode();
1169                         *tnode->head = tnode;
1170                 }
1171                 lhead->next = tnode;
1172                 tnode->prev = lhead;
1173                 tnode->left = tnode->right = NULL;
1174
1175                 if ( lhead->parent ) {
1176                         if ( lhead->parent->left == lhead ) { /* lhead is guaranteed to by the NYT */
1177                                 lhead->parent->left = tnode2;
1178                         } else {
1179                                 lhead->parent->right = tnode2;
1180                         }
1181                 } else {
1182                         tree = tnode2;
1183                 }
1184
1185                 tnode2->right = tnode;
1186                 tnode2->left = lhead;
1187
1188                 tnode2->parent = lhead->parent;
1189                 lhead->parent = tnode->parent = tnode2;
1190
1191                 loc[ch] = tnode;
1192
1193                 Increment( tnode2->parent );
1194         } else {
1195                 Increment( loc[ch] );
1196         }
1197 }
1198
1199 /*
1200 ================
1201 idCompressor_Huffman::Receive
1202
1203   Get a symbol.
1204 ================
1205 */
1206 int idCompressor_Huffman::Receive( huffmanNode_t *node, int *ch ) {
1207         while ( node && node->symbol == INTERNAL_NODE ) {
1208                 if ( Get_bit() ) {
1209                         node = node->right;
1210                 } else {
1211                         node = node->left;
1212                 }
1213         }
1214         if ( !node ) {
1215                 return 0;
1216         }
1217         return (*ch = node->symbol);
1218 }
1219
1220 /*
1221 ================
1222 idCompressor_Huffman::Send
1223
1224   Send the prefix code for this node.
1225 ================
1226 */
1227 void idCompressor_Huffman::Send( huffmanNode_t *node, huffmanNode_t *child, byte *fout ) {
1228         if ( node->parent ) {
1229                 Send( node->parent, node, fout );
1230         }
1231         if ( child ) {
1232                 if ( node->right == child ) {
1233                         Add_bit( 1, fout );
1234                 } else {
1235                         Add_bit( 0, fout );
1236                 }
1237         }
1238 }
1239
1240 /*
1241 ================
1242 idCompressor_Huffman::Transmit
1243
1244   Send a symbol.
1245 ================
1246 */
1247 void idCompressor_Huffman::Transmit( int ch, byte *fout ) {
1248         int i;
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 );
1254                 }
1255         } else {
1256                 Send( loc[ch], NULL, fout );
1257         }
1258 }
1259
1260 /*
1261 ================
1262 idCompressor_Huffman::Write
1263 ================
1264 */
1265 int idCompressor_Huffman::Write( const void *inData, int inLength ) {
1266         int i, ch;
1267
1268         if ( compress == false || inLength <= 0 ) {
1269                 return 0;
1270         }
1271
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 */
1276                 int b = (bloc>>3);
1277                 if ( b > 32768 ) {
1278                         file->Write( seq, b );
1279                         seq[0] = seq[b];
1280                         bloc &= 7;
1281                         compressedSize += b;
1282                 }
1283         }
1284
1285         unCompressedSize += i;
1286         return i;
1287 }
1288
1289 /*
1290 ================
1291 idCompressor_Huffman::FinishCompress
1292 ================
1293 */
1294 void idCompressor_Huffman::FinishCompress( void ) {
1295
1296         if ( compress == false ) {
1297                 return;
1298         }
1299
1300         bloc += 7;
1301         int str = (bloc>>3);
1302         if ( str ) {
1303                 file->Write( seq, str );
1304                 compressedSize += str;
1305         }
1306 }
1307
1308 /*
1309 ================
1310 idCompressor_Huffman::Read
1311 ================
1312 */
1313 int idCompressor_Huffman::Read( void *outData, int outLength ) {
1314         int i, j, ch;
1315
1316         if ( compress == true || outLength <= 0 ) {
1317                 return 0;
1318         }
1319
1320         if ( bloc == 0 ) {
1321                 blocMax = file->Read( seq, sizeof( seq ) );
1322                 blocIn = 0;
1323         }
1324
1325         for ( i = 0; i < outLength; i++ ) {
1326                 ch = 0;
1327                 // don't overflow reading from the file
1328                 if ( ( bloc >> 3 ) > blocMax ) {
1329                         break;
1330                 }
1331                 Receive( tree, &ch );                           /* Get a character */
1332                 if ( ch == NYT ) {                                      /* We got a NYT, get the symbol associated with it */
1333                         ch = 0;
1334                         for ( j = 0; j < 8; j++ ) {
1335                                 ch = ( ch << 1 ) + Get_bit();
1336                         }
1337                 }
1338
1339                 ((byte *)outData)[i] = ch;                      /* Write symbol */
1340                 AddRef( (byte) ch );                            /* Increment node */
1341         }
1342
1343         compressedSize = bloc >> 3;
1344         unCompressedSize += i;
1345         return i;
1346 }
1347
1348 /*
1349 ================
1350 idCompressor_Huffman::GetCompressionRatio
1351 ================
1352 */
1353 float idCompressor_Huffman::GetCompressionRatio( void ) const {
1354         return ( unCompressedSize - compressedSize ) * 100.0f / unCompressedSize;
1355 }
1356
1357
1358 /*
1359 =================================================================================
1360
1361         idCompressor_Arithmetic
1362
1363         The following algorithm is based on the Arithmetic Coding methods described
1364         by Mark Nelson. The probability table is implicitly stored.
1365
1366 =================================================================================
1367 */
1368
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;
1377
1378 class idCompressor_Arithmetic : public idCompressor_BitStream {
1379 public:
1380                                         idCompressor_Arithmetic( void ) {}
1381
1382         void                    Init( idFile *f, bool compress, int wordLength );
1383         void                    FinishCompress( void );
1384
1385         int                             Write( const void *inData, int inLength );
1386         int                             Read( void *outData, int outLength );
1387
1388 private:
1389                                         typedef struct acProbs_s {
1390                                                 unsigned int    low;
1391                                                 unsigned int    high;
1392                                         } acProbs_t;
1393
1394                                         typedef struct acSymbol_s {
1395                                                 unsigned int    low;
1396                                                 unsigned int    high;
1397                                                 int                             position;
1398                                         } acSymbol_t;
1399
1400         acProbs_t               probabilities[1<<AC_WORD_LENGTH];
1401
1402         int                             symbolBuffer;
1403         int                             symbolBit;
1404
1405         unsigned short  low;
1406         unsigned short  high;
1407         unsigned short  code;
1408         unsigned int    underflowBits;
1409         unsigned int    scale;
1410
1411 private:
1412         void                    InitProbabilities( void );
1413         void                    UpdateProbabilities( acSymbol_t* symbol );
1414         int                             ProbabilityForCount( unsigned int count );
1415
1416         void                    CharToSymbol( byte c, acSymbol_t* symbol );
1417         void                    EncodeSymbol( acSymbol_t* symbol );
1418
1419         int                             SymbolFromCount( unsigned int count, acSymbol_t* symbol );
1420         int                             GetCurrentCount( void );
1421         void                    RemoveSymbolFromStream( acSymbol_t* symbol );
1422
1423         void                    PutBit( int bit );
1424         int                             GetBit( void );
1425
1426         void                    WriteOverflowBits( void );
1427 };
1428
1429 /*
1430 ================
1431 idCompressor_Arithmetic::Init
1432 ================
1433 */
1434 void idCompressor_Arithmetic::Init( idFile *f, bool compress, int wordLength ) {
1435         idCompressor_BitStream::Init( f, compress, wordLength );
1436
1437         symbolBuffer    = 0;
1438         symbolBit               = 0;
1439 }
1440
1441 /*
1442 ================
1443 idCompressor_Arithmetic::InitProbabilities
1444 ================
1445 */
1446 void idCompressor_Arithmetic::InitProbabilities( void ) {
1447         high                    = AC_HIGH_INIT;
1448         low                             = AC_LOW_INIT;
1449         underflowBits   = 0;
1450         code                    = 0;
1451
1452         for( int i = 0; i < (1<<AC_WORD_LENGTH); i++ ) {
1453                 probabilities[ i ].low = i;
1454                 probabilities[ i ].high = i + 1;
1455         }
1456
1457         scale = (1<<AC_WORD_LENGTH);
1458 }
1459
1460 /*
1461 ================
1462 idCompressor_Arithmetic::UpdateProbabilities
1463 ================
1464 */
1465 void idCompressor_Arithmetic::UpdateProbabilities( acSymbol_t* symbol ) {
1466         int i, x;
1467
1468         x = symbol->position;
1469
1470         probabilities[ x ].high++;
1471
1472         for( i = x + 1; i < (1<<AC_WORD_LENGTH); i++ ) {
1473                 probabilities[ i ].low++;
1474                 probabilities[ i ].high++;
1475         }
1476
1477         scale++;
1478 }
1479
1480 /*
1481 ================
1482 idCompressor_Arithmetic::GetCurrentCount
1483 ================
1484 */
1485 int idCompressor_Arithmetic::GetCurrentCount( void ) {
1486     return (unsigned int) ( ( ( ( (long) code - low ) + 1 ) * scale - 1 ) / ( ( (long) high - low ) + 1 ) );
1487 }
1488
1489 /*
1490 ================
1491 idCompressor_Arithmetic::ProbabilityForCount
1492 ================
1493 */
1494 int idCompressor_Arithmetic::ProbabilityForCount( unsigned int count ) {
1495 #if 1
1496
1497         int len, mid, offset, res;
1498
1499         len = (1<<AC_WORD_LENGTH);
1500         mid = len;
1501         offset = 0;
1502         res = 0;
1503         while( mid > 0 ) {
1504                 mid = len >> 1;
1505                 if ( count >= probabilities[offset+mid].high ) {
1506                         offset += mid;
1507                         len -= mid;
1508                         res = 1;
1509                 }
1510                 else if ( count < probabilities[offset+mid].low ) {
1511                         len -= mid;
1512                         res = 0;
1513                 } else {
1514                         return offset+mid;
1515                 }
1516         }
1517         return offset+res;
1518
1519 #else
1520
1521         int j;
1522
1523         for( j = 0; j < (1<<AC_WORD_LENGTH); j++ ) {
1524         if ( count >= probabilities[ j ].low && count < probabilities[ j ].high ) {
1525                         return j;
1526         }
1527     }
1528
1529         assert( false );
1530
1531         return 0;
1532
1533 #endif
1534 }
1535
1536 /*
1537 ================
1538 idCompressor_Arithmetic::SymbolFromCount
1539 ================
1540 */
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;
1546     return p;
1547 }
1548
1549 /*
1550 ================
1551 idCompressor_Arithmetic::RemoveSymbolFromStream
1552 ================
1553 */
1554 void idCompressor_Arithmetic::RemoveSymbolFromStream( acSymbol_t* symbol ) {
1555     long range;
1556
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 );
1560
1561     while( true ) {
1562
1563         if ( ( high & AC_MSB_MASK ) == ( low & AC_MSB_MASK ) ) {
1564
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;
1569                 } else {
1570                         UpdateProbabilities( symbol );
1571             return;
1572                 }
1573
1574         low <<= 1;
1575         high <<= 1;
1576         high |= 1;
1577         code <<= 1;
1578         code |= ReadBits( 1 );
1579     }
1580 }
1581
1582 /*
1583 ================
1584 idCompressor_Arithmetic::GetBit
1585 ================
1586 */
1587 int idCompressor_Arithmetic::GetBit( void ) {
1588         int getbit;
1589
1590         if( symbolBit <= 0 ) {
1591                 // read a new symbol out
1592                 acSymbol_t symbol;
1593                 symbolBuffer = SymbolFromCount( GetCurrentCount(), &symbol );
1594                 RemoveSymbolFromStream( &symbol );
1595                 symbolBit = AC_WORD_LENGTH;
1596         }
1597
1598         getbit = ( symbolBuffer >> ( AC_WORD_LENGTH - symbolBit ) ) & 1;
1599         symbolBit--;
1600
1601         return getbit;
1602 }
1603
1604 /*
1605 ================
1606 idCompressor_Arithmetic::EncodeSymbol
1607 ================
1608 */
1609 void idCompressor_Arithmetic::EncodeSymbol( acSymbol_t* symbol ) {
1610         unsigned int range;
1611
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 );
1616
1617         while( true ) {
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 );
1621
1622             while( underflowBits > 0 ) {
1623
1624                                 WriteBits( ~high >> AC_MSB_SHIFT, 1 );
1625
1626                                 underflowBits--;
1627             }
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
1630                         underflowBits   += 1;
1631                         low                             &= AC_MSB2_MASK - 1;
1632                         high                    |= AC_MSB2_MASK;
1633                 } else {
1634                         UpdateProbabilities( symbol );
1635             return;
1636                 }
1637
1638         low <<= 1;
1639         high <<= 1;
1640         high |= 1;
1641     }
1642 }
1643
1644 /*
1645 ================
1646 idCompressor_Arithmetic::CharToSymbol
1647 ================
1648 */
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;
1653 }
1654
1655 /*
1656 ================
1657 idCompressor_Arithmetic::PutBit
1658 ================
1659 */
1660 void idCompressor_Arithmetic::PutBit( int putbit ) {
1661         symbolBuffer |= ( putbit & 1 ) << symbolBit;
1662         symbolBit++;
1663
1664         if( symbolBit >= AC_WORD_LENGTH ) {
1665                 acSymbol_t symbol;
1666
1667                 CharToSymbol( symbolBuffer, &symbol );
1668                 EncodeSymbol( &symbol );
1669
1670                 symbolBit = 0;
1671                 symbolBuffer = 0;
1672         }
1673 }
1674
1675 /*
1676 ================
1677 idCompressor_Arithmetic::WriteOverflowBits
1678 ================
1679 */
1680 void idCompressor_Arithmetic::WriteOverflowBits( void ) {
1681
1682         WriteBits( low >> AC_MSB2_SHIFT, 1 );
1683
1684         underflowBits++;
1685         while( underflowBits-- > 0 ) {
1686                 WriteBits( ~low >> AC_MSB2_SHIFT, 1 );
1687         }
1688 }
1689
1690 /*
1691 ================
1692 idCompressor_Arithmetic::Write
1693 ================
1694 */
1695 int idCompressor_Arithmetic::Write( const void *inData, int inLength ) {
1696         int i, j;
1697
1698         if ( compress == false || inLength <= 0 ) {
1699                 return 0;
1700         }
1701
1702         InitCompress( inData, inLength );
1703
1704         for( i = 0; i < inLength; i++ ) {
1705                 if ( ( readTotalBytes & ( ( 1 << 14 ) - 1 ) ) == 0 ) {
1706                         if ( readTotalBytes ) {
1707                                 WriteOverflowBits();
1708                                 WriteBits( 0, 15 );
1709                                 while( writeBit ) {
1710                                         WriteBits( 0, 1 );
1711                                 }
1712                                 WriteBits( 255, 8 );
1713                         }
1714                         InitProbabilities();
1715                 }
1716                 for ( j = 0; j < 8; j++ ) {
1717                         PutBit( ReadBits( 1 ) );
1718                 }
1719         }
1720
1721         return inLength;
1722 }
1723
1724 /*
1725 ================
1726 idCompressor_Arithmetic::FinishCompress
1727 ================
1728 */
1729 void idCompressor_Arithmetic::FinishCompress( void ) {
1730         if ( compress == false ) {
1731                 return;
1732         }
1733
1734         WriteOverflowBits();
1735
1736         idCompressor_BitStream::FinishCompress();
1737 }
1738
1739 /*
1740 ================
1741 idCompressor_Arithmetic::Read
1742 ================
1743 */
1744 int idCompressor_Arithmetic::Read( void *outData, int outLength ) {
1745         int i, j;
1746
1747         if ( compress == true || outLength <= 0 ) {
1748                 return 0;
1749         }
1750
1751         InitDecompress( outData, outLength );
1752
1753         for( i = 0; i < outLength && readLength >= 0; i++ ) {
1754                 if ( ( writeTotalBytes & ( ( 1 << 14 ) - 1 ) ) == 0 ) {
1755                         if ( writeTotalBytes ) {
1756                                 while( readBit ) {
1757                                         ReadBits( 1 );
1758                                 }
1759                                 while( ReadBits( 8 ) == 0 && readLength > 0 ) {
1760                                 }
1761                         }
1762                         InitProbabilities();
1763                         for ( j = 0; j < AC_NUM_BITS; j++ ) {
1764                                 code <<= 1;
1765                                 code |= ReadBits( 1 );
1766                         }
1767                 }
1768                 for ( j = 0; j < 8; j++ ) {
1769                         WriteBits( GetBit(), 1 );
1770                 }
1771         }
1772
1773         return i;
1774 }
1775
1776
1777 /*
1778 =================================================================================
1779
1780         idCompressor_LZSS
1781
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
1785         text.
1786
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.
1793
1794         The following algorithm is an implementation of LZSS with arbitrary word size.
1795
1796 =================================================================================
1797 */
1798
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;
1805
1806 class idCompressor_LZSS : public idCompressor_BitStream {
1807 public:
1808                                         idCompressor_LZSS( void ) {}
1809
1810         void                    Init( idFile *f, bool compress, int wordLength );
1811         void                    FinishCompress( void );
1812
1813         int                             Write( const void *inData, int inLength );
1814         int                             Read( void *outData, int outLength );
1815
1816 protected:
1817         int                             offsetBits;
1818         int                             lengthBits;
1819         int                             minMatchWords;
1820
1821         byte                    block[LZSS_BLOCK_SIZE];
1822         int                             blockSize;
1823         int                             blockIndex;
1824
1825         int                             hashTable[LZSS_HASH_SIZE];
1826         int                             hashNext[LZSS_BLOCK_SIZE * 8];
1827
1828 protected:
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 );
1834 };
1835
1836 /*
1837 ================
1838 idCompressor_LZSS::Init
1839 ================
1840 */
1841 void idCompressor_LZSS::Init( idFile *f, bool compress, int wordLength ) {
1842         idCompressor_BitStream::Init( f, compress, wordLength );
1843
1844         offsetBits = LZSS_OFFSET_BITS;
1845         lengthBits = LZSS_LENGTH_BITS;
1846
1847         minMatchWords = ( offsetBits + lengthBits + wordLength ) / wordLength;
1848         blockSize = 0;
1849         blockIndex = 0;
1850 }
1851
1852 /*
1853 ================
1854 idCompressor_LZSS::FindMatch
1855 ================
1856 */
1857 bool idCompressor_LZSS::FindMatch( int startWord, int startValue, int &wordOffset, int &numWords ) {
1858         int i, n, hash, bottom, maxBits;
1859
1860         wordOffset = startWord;
1861         numWords = minMatchWords - 1;
1862
1863         bottom = Max( 0, startWord - ( ( 1 << offsetBits ) - 1 ) );
1864         maxBits = ( blockSize << 3 ) - startWord * wordLength;
1865
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;
1871                         wordOffset = i;
1872                         if ( numWords > ( ( 1 << lengthBits ) - 1 + minMatchWords ) - 1 ) {
1873                                 numWords = ( ( 1 << lengthBits ) - 1 + minMatchWords ) - 1;
1874                                 break;
1875                         }
1876                 }
1877         }
1878
1879         return ( numWords >= minMatchWords );
1880 }
1881
1882 /*
1883 ================
1884 idCompressor_LZSS::AddToHash
1885 ================
1886 */
1887 void idCompressor_LZSS::AddToHash( int index, int hash ) {
1888         hashNext[index] = hashTable[hash];
1889         hashTable[hash] = index;
1890 }
1891
1892 /*
1893 ================
1894 idCompressor_LZSS::GetWordFromBlock
1895 ================
1896 */
1897 int idCompressor_LZSS::GetWordFromBlock( int wordOffset ) const {
1898         int blockBit, blockByte, value, valueBits, get, fraction;
1899
1900         blockBit = ( wordOffset * wordLength ) & 7;
1901         blockByte = ( wordOffset * wordLength ) >> 3;
1902         if ( blockBit != 0 ) {
1903                 blockByte++;
1904         }
1905
1906         value = 0;
1907         valueBits = 0;
1908
1909         while ( valueBits < wordLength ) {
1910                 if ( blockBit == 0 ) {
1911                         if ( blockByte >= LZSS_BLOCK_SIZE ) {
1912                                 return value;
1913                         }
1914                         blockByte++;
1915                 }
1916                 get = 8 - blockBit;
1917                 if ( get > (wordLength - valueBits) ) {
1918                         get = (wordLength - valueBits);
1919                 }
1920                 fraction = block[blockByte - 1];
1921                 fraction >>= blockBit;
1922                 fraction &= ( 1 << get ) - 1;
1923                 value |= fraction << valueBits;
1924                 valueBits += get;
1925                 blockBit = ( blockBit + get ) & 7;
1926         }
1927
1928         return value;
1929 }
1930
1931 /*
1932 ================
1933 idCompressor_LZSS::CompressBlock
1934 ================
1935 */
1936 void idCompressor_LZSS::CompressBlock( void ) {
1937         int i, startWord, startValue, wordOffset, numWords;
1938
1939         InitCompress( block, blockSize );
1940
1941         memset( hashTable, -1, sizeof( hashTable ) );
1942         memset( hashNext, -1, sizeof( hashNext ) );
1943
1944         startWord = 0;
1945         while( readByte < readLength ) {
1946                 startValue = ReadBits( wordLength );
1947                 if ( FindMatch( startWord, startValue, wordOffset, numWords ) ) {
1948                         WriteBits( 1, 1 );
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 );
1955                                 startWord++;
1956                         }
1957                 } else {
1958                         WriteBits( 0, 1 );
1959                         WriteBits( startValue, wordLength );
1960                         AddToHash( startWord, startValue & LZSS_HASH_MASK );
1961                         startWord++;
1962                 }
1963         }
1964
1965         blockSize = 0;
1966 }
1967
1968 /*
1969 ================
1970 idCompressor_LZSS::DecompressBlock
1971 ================
1972 */
1973 void idCompressor_LZSS::DecompressBlock( void ) {
1974         int i, offset, startWord, numWords;
1975
1976         InitDecompress( block, LZSS_BLOCK_SIZE );
1977
1978         startWord = 0;
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 );
1985                                 startWord++;
1986                         }
1987                 } else {
1988                         WriteBits( ReadBits( wordLength ), wordLength );
1989                         startWord++;
1990                 }
1991         }
1992
1993         blockSize = Min( writeByte, LZSS_BLOCK_SIZE );
1994 }
1995
1996 /*
1997 ================
1998 idCompressor_LZSS::Write
1999 ================
2000 */
2001 int idCompressor_LZSS::Write( const void *inData, int inLength ) {
2002         int i, n;
2003
2004         if ( compress == false || inLength <= 0 ) {
2005                 return 0;
2006         }
2007
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;
2013                         CompressBlock();
2014                         blockSize = 0;
2015                 } else {
2016                         memcpy( block + blockSize, ((const byte *)inData) + i, inLength - i );
2017                         n = inLength - i;
2018                         blockSize += n;
2019                 }
2020         }
2021
2022         return inLength;
2023 }
2024
2025 /*
2026 ================
2027 idCompressor_LZSS::FinishCompress
2028 ================
2029 */
2030 void idCompressor_LZSS::FinishCompress( void ) {
2031         if ( compress == false ) {
2032                 return;
2033         }
2034         if ( blockSize ) {
2035                 CompressBlock();
2036         }
2037         idCompressor_BitStream::FinishCompress();
2038 }
2039
2040 /*
2041 ================
2042 idCompressor_LZSS::Read
2043 ================
2044 */
2045 int idCompressor_LZSS::Read( void *outData, int outLength ) {
2046         int i, n;
2047
2048         if ( compress == true || outLength <= 0 ) {
2049                 return 0;
2050         }
2051
2052         if ( !blockSize ) {
2053                 DecompressBlock();
2054         }
2055
2056         for ( n = i = 0; i < outLength; i += n ) {
2057                 if ( !blockSize ) {
2058                         return i;
2059                 }
2060                 n = blockSize - blockIndex;
2061                 if ( outLength - i >= n ) {
2062                         memcpy( ((byte *)outData) + i, block + blockIndex, n );
2063                         DecompressBlock();
2064                         blockIndex = 0;
2065                 } else {
2066                         memcpy( ((byte *)outData) + i, block + blockIndex, outLength - i );
2067                         n = outLength - i;
2068                         blockIndex += n;
2069                 }
2070         }
2071
2072         return outLength;
2073 }
2074
2075 /*
2076 =================================================================================
2077
2078         idCompressor_LZSS_WordAligned
2079
2080         Outputs word aligned compressed data.
2081
2082 =================================================================================
2083 */
2084
2085 class idCompressor_LZSS_WordAligned : public idCompressor_LZSS {
2086 public:
2087                                         idCompressor_LZSS_WordAligned( void ) {}
2088
2089         void                    Init( idFile *f, bool compress, int wordLength );
2090 private:
2091         virtual void    CompressBlock( void );
2092         virtual void    DecompressBlock( void );
2093 };
2094
2095 /*
2096 ================
2097 idCompressor_LZSS_WordAligned::Init
2098 ================
2099 */
2100 void idCompressor_LZSS_WordAligned::Init( idFile *f, bool compress, int wordLength ) {
2101         idCompressor_LZSS::Init( f, compress, wordLength );
2102
2103         offsetBits = 2 * wordLength;
2104         lengthBits = wordLength;
2105
2106         minMatchWords = ( offsetBits + lengthBits + wordLength ) / wordLength;
2107         blockSize = 0;
2108         blockIndex = 0;
2109 }
2110
2111 /*
2112 ================
2113 idCompressor_LZSS_WordAligned::CompressBlock
2114 ================
2115 */
2116 void idCompressor_LZSS_WordAligned::CompressBlock( void ) {
2117         int i, startWord, startValue, wordOffset, numWords;
2118
2119         InitCompress( block, blockSize );
2120
2121         memset( hashTable, -1, sizeof( hashTable ) );
2122         memset( hashNext, -1, sizeof( hashNext ) );
2123
2124         startWord = 0;
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 );
2134                                 startWord++;
2135                         }
2136                 } else {
2137                         WriteBits( 0, lengthBits );
2138                         WriteBits( startValue, wordLength );
2139                         AddToHash( startWord, startValue & LZSS_HASH_MASK );
2140                         startWord++;
2141                 }
2142         }
2143
2144         blockSize = 0;
2145 }
2146
2147 /*
2148 ================
2149 idCompressor_LZSS_WordAligned::DecompressBlock
2150 ================
2151 */
2152 void idCompressor_LZSS_WordAligned::DecompressBlock( void ) {
2153         int i, offset, startWord, numWords;
2154
2155         InitDecompress( block, LZSS_BLOCK_SIZE );
2156
2157         startWord = 0;
2158         while( writeByte < writeLength && readLength >= 0 ) {
2159                 numWords = ReadBits( lengthBits );
2160                 if ( numWords ) {
2161                         numWords += ( minMatchWords - 1 );
2162                         offset = startWord - ReadBits( offsetBits );
2163                         for ( i = 0; i < numWords; i++ ) {
2164                                 WriteBits( GetWordFromBlock( offset + i ), wordLength );
2165                                 startWord++;
2166                         }
2167                 } else {
2168                         WriteBits( ReadBits( wordLength ), wordLength );
2169                         startWord++;
2170                 }
2171         }
2172
2173         blockSize = Min( writeByte, LZSS_BLOCK_SIZE );
2174 }
2175
2176 /*
2177 =================================================================================
2178
2179         idCompressor_LZW
2180
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
2186
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.
2190
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
2199         previous string).
2200
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.
2208
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.
2213
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.
2218
2219         Dictionary entries 0-255 are always going to have the values 0-255
2220
2221 =================================================================================
2222 */
2223
2224 class idCompressor_LZW : public idCompressor_BitStream {
2225 public:
2226                                         idCompressor_LZW( void ) {}
2227
2228         void                    Init( idFile *f, bool compress, int wordLength );
2229         void                    FinishCompress( void );
2230
2231         int                             Write( const void *inData, int inLength );
2232         int                             Read( void *outData, int outLength );
2233
2234 protected:
2235         int                             AddToDict( int w, int k );
2236         int                             Lookup( int w, int k );
2237
2238         bool                    BumpBits();
2239
2240         int                             WriteChain( int code );
2241         void                    DecompressBlock();
2242
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;
2248
2249         // Dictionary data
2250         struct {
2251                 int k;
2252                 int w;
2253         }                               dictionary[LZW_DICT_SIZE];
2254         idHashIndex             index;
2255
2256         int                             nextCode;
2257         int                             codeBits;
2258
2259         // Block data
2260         byte                    block[LZW_BLOCK_SIZE];
2261         int                             blockSize;
2262         int                             blockIndex;
2263
2264         // Used by the compressor
2265         int                             w;
2266
2267         // Used by the decompressor
2268         int                             oldCode;
2269 };
2270
2271 /*
2272 ================
2273 idCompressor_LZW::Init
2274 ================
2275 */
2276 void idCompressor_LZW::Init( idFile *f, bool compress, int wordLength ) {
2277         idCompressor_BitStream::Init( f, compress, wordLength );
2278
2279         for ( int i=0; i<LZW_FIRST_CODE; i++ ) {
2280                 dictionary[i].k = i;
2281                 dictionary[i].w = -1;
2282         }
2283         index.Clear();
2284
2285         nextCode = LZW_FIRST_CODE;
2286         codeBits = LZW_START_BITS;
2287
2288         blockSize = 0;
2289         blockIndex = 0;
2290
2291         w = -1;
2292         oldCode = -1;
2293 }
2294
2295 /*
2296 ================
2297 idCompressor_LZW::Read
2298 ================
2299 */
2300 int idCompressor_LZW::Read( void *outData, int outLength ) {
2301         int i, n;
2302
2303         if ( compress == true || outLength <= 0 ) {
2304                 return 0;
2305         }
2306
2307         if ( !blockSize ) {
2308                 DecompressBlock();
2309         }
2310
2311         for ( n = i = 0; i < outLength; i += n ) {
2312                 if ( !blockSize ) {
2313                         return i;
2314                 }
2315                 n = blockSize - blockIndex;
2316                 if ( outLength - i >= n ) {
2317                         memcpy( ((byte *)outData) + i, block + blockIndex, n );
2318                         DecompressBlock();
2319                         blockIndex = 0;
2320                 } else {
2321                         memcpy( ((byte *)outData) + i, block + blockIndex, outLength - i );
2322                         n = outLength - i;
2323                         blockIndex += n;
2324                 }
2325         }
2326
2327         return outLength;
2328 }
2329
2330 /*
2331 ================
2332 idCompressor_LZW::Lookup
2333 ================
2334 */
2335 int idCompressor_LZW::Lookup( int w, int k ) {
2336         int j;
2337
2338         if ( w == -1 ) {
2339                 return k;
2340         } else {
2341                 for ( j = index.First( w ^ k ); j >= 0 ; j = index.Next( j ) ) {
2342                         if ( dictionary[ j ].k == k && dictionary[ j ].w == w ) {
2343                                 return j;
2344                         }
2345                 }
2346         }
2347
2348         return -1;
2349 }
2350
2351 /*
2352 ================
2353 idCompressor_LZW::AddToDict
2354 ================
2355 */
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 );
2360         return nextCode++;
2361 }
2362
2363 /*
2364 ================
2365 idCompressor_LZW::BumpBits
2366
2367 Possibly increments codeBits
2368 Returns true if the dictionary was cleared
2369 ================
2370 */
2371 bool idCompressor_LZW::BumpBits() {
2372         if ( nextCode == ( 1 << codeBits ) ) {
2373                 codeBits ++;
2374                 if ( codeBits > LZW_DICT_BITS ) {
2375                         nextCode = LZW_FIRST_CODE;
2376                         codeBits = LZW_START_BITS;
2377                         index.Clear();
2378                         return true;
2379                 }
2380         }
2381         return false;
2382 }
2383
2384 /*
2385 ================
2386 idCompressor_LZW::FinishCompress
2387 ================
2388 */
2389 void idCompressor_LZW::FinishCompress( void ) {
2390         WriteBits( w, codeBits );
2391         idCompressor_BitStream::FinishCompress();
2392 }
2393
2394 /*
2395 ================
2396 idCompressor_LZW::Write
2397 ================
2398 */
2399 int idCompressor_LZW::Write( const void *inData, int inLength ) {
2400         int i;
2401
2402         InitCompress( inData, inLength );
2403
2404         for ( i = 0; i < inLength; i++ ) {
2405                 int k = ReadBits( 8 );
2406
2407                 int code = Lookup(w, k);
2408                 if ( code >= 0 ) {
2409                         w = code;
2410                 } else {
2411                         WriteBits( w, codeBits );
2412                         if ( !BumpBits() ) {
2413                                 AddToDict( w, k );
2414                         }
2415                         w = k;
2416                 }
2417         }
2418
2419         return inLength;
2420 }
2421
2422
2423 /*
2424 ================
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
2427 ================
2428 */
2429 int idCompressor_LZW::WriteChain( int code ) {
2430         byte chain[LZW_DICT_SIZE];
2431         int firstChar = 0;
2432         int i = 0;
2433         do {
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 );
2441         }
2442         return firstChar;
2443 }
2444
2445 /*
2446 ================
2447 idCompressor_LZW::DecompressBlock
2448 ================
2449 */
2450 void idCompressor_LZW::DecompressBlock() {
2451         int code, firstChar;
2452
2453         InitDecompress( block, LZW_BLOCK_SIZE );
2454
2455         while( writeByte < writeLength - LZW_DICT_SIZE && readLength > 0 ) {
2456                 assert( codeBits <= LZW_DICT_BITS );
2457
2458                 code = ReadBits( codeBits );
2459                 if ( readLength == 0 ) {
2460                         break;
2461                 }
2462
2463                 if ( oldCode == -1 ) {
2464                         assert( code < 256 );
2465                         WriteBits( code, 8 );
2466                         oldCode = code;
2467                         firstChar = code;
2468                         continue;
2469                 }
2470
2471                 if ( code >= nextCode ) {
2472                         assert( code == nextCode );
2473                         firstChar = WriteChain( oldCode );
2474                         WriteBits( firstChar, 8 );
2475                 } else {
2476                         firstChar = WriteChain( code );
2477                 }
2478                 AddToDict( oldCode, firstChar );
2479                 if ( BumpBits() ) {
2480                         oldCode = -1;
2481                 } else {
2482                         oldCode = code;
2483                 }
2484         }
2485
2486         blockSize = Min( writeByte, LZW_BLOCK_SIZE );
2487 }
2488
2489 /*
2490 =================================================================================
2491
2492         idCompressor
2493
2494 =================================================================================
2495 */
2496
2497 /*
2498 ================
2499 idCompressor::AllocNoCompression
2500 ================
2501 */
2502 idCompressor * idCompressor::AllocNoCompression( void ) {
2503         return new idCompressor_None();
2504 }
2505
2506 /*
2507 ================
2508 idCompressor::AllocBitStream
2509 ================
2510 */
2511 idCompressor * idCompressor::AllocBitStream( void ) {
2512         return new idCompressor_BitStream();
2513 }
2514
2515 /*
2516 ================
2517 idCompressor::AllocRunLength
2518 ================
2519 */
2520 idCompressor * idCompressor::AllocRunLength( void ) {
2521         return new idCompressor_RunLength();
2522 }
2523
2524 /*
2525 ================
2526 idCompressor::AllocRunLength_ZeroBased
2527 ================
2528 */
2529 idCompressor * idCompressor::AllocRunLength_ZeroBased( void ) {
2530         return new idCompressor_RunLength_ZeroBased();
2531 }
2532
2533 /*
2534 ================
2535 idCompressor::AllocHuffman
2536 ================
2537 */
2538 idCompressor * idCompressor::AllocHuffman( void ) {
2539         return new idCompressor_Huffman();
2540 }
2541
2542 /*
2543 ================
2544 idCompressor::AllocArithmetic
2545 ================
2546 */
2547 idCompressor * idCompressor::AllocArithmetic( void ) {
2548         return new idCompressor_Arithmetic();
2549 }
2550
2551 /*
2552 ================
2553 idCompressor::AllocLZSS
2554 ================
2555 */
2556 idCompressor * idCompressor::AllocLZSS( void ) {
2557         return new idCompressor_LZSS();
2558 }
2559
2560 /*
2561 ================
2562 idCompressor::AllocLZSS_WordAligned
2563 ================
2564 */
2565 idCompressor * idCompressor::AllocLZSS_WordAligned( void ) {
2566         return new idCompressor_LZSS_WordAligned();
2567 }
2568
2569 /*
2570 ================
2571 idCompressor::AllocLZW
2572 ================
2573 */
2574 idCompressor * idCompressor::AllocLZW( void ) {
2575         return new idCompressor_LZW();
2576 }