bitStream.cpp

Public Functions

IsEqual(F32 a, F32 b)

   1
   2//-----------------------------------------------------------------------------
   3// Copyright (c) 2012 GarageGames, LLC
   4//
   5// Permission is hereby granted, free of charge, to any person obtaining a copy
   6// of this software and associated documentation files (the "Software"), to
   7// deal in the Software without restriction, including without limitation the
   8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
   9// sell copies of the Software, and to permit persons to whom the Software is
  10// furnished to do so, subject to the following conditions:
  11//
  12// The above copyright notice and this permission notice shall be included in
  13// all copies or substantial portions of the Software.
  14//
  15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  21// IN THE SOFTWARE.
  22//-----------------------------------------------------------------------------
  23
  24#include "platform/platform.h"
  25#include "core/stream/bitStream.h"
  26
  27#include "core/strings/stringFunctions.h"
  28#include "math/mathIO.h"
  29#include "console/consoleObject.h"
  30#include "platform/platformNet.h"
  31#include "core/bitVector.h"
  32
  33
  34static BitStream gPacketStream(NULL, 0);
  35static U8 gPacketBuffer[Net::MaxPacketDataSize];
  36
  37// bitstream utility functions
  38
  39void BitStream::clearStringBuffer() 
  40{
  41   static char stringBuf[256];
  42   stringBuf[0] = 0; 
  43//   setStringBuffer( stringBuf ); 
  44}
  45
  46void BitStream::setStringBuffer(char buffer[256])
  47{
  48//   stringBuffer = buffer;
  49}
  50
  51BitStream *BitStream::getPacketStream(U32 writeSize)
  52{
  53   if(!writeSize)
  54      writeSize = Net::MaxPacketDataSize;
  55
  56   gPacketStream.setBuffer(gPacketBuffer, writeSize, Net::MaxPacketDataSize);
  57   gPacketStream.setPosition(0);
  58
  59   return &gPacketStream;
  60}
  61
  62void BitStream::sendPacketStream(const NetAddress *addr)
  63{
  64   Net::sendto(addr, gPacketStream.getBuffer(), gPacketStream.getPosition());
  65}
  66
  67// CodeReview WTF is this additional IsEqual? - BJG, 3/29/07
  68
  69inline bool IsEqual(F32 a, F32 b) { return a == b; }
  70
  71ResizeBitStream::ResizeBitStream(U32 minSpace, U32 initialSize) : BitStream(NULL, 0, 0)
  72{
  73   mMinSpace = minSpace;
  74   if(!initialSize)
  75      initialSize = minSpace * 2;
  76   U8 *buf = (U8 *) dMalloc(initialSize);
  77   setBuffer(buf, initialSize, initialSize);
  78}
  79
  80ResizeBitStream::~ResizeBitStream()
  81{
  82   dFree(dataPtr);
  83}
  84
  85void ResizeBitStream::validate()
  86{
  87   if(getPosition() + mMinSpace > bufSize)
  88   {
  89      bufSize = getPosition() + mMinSpace * 2;
  90      dataPtr = (U8 *) dRealloc(dataPtr, bufSize);
  91
  92      maxReadBitNum = bufSize << 3;
  93      maxWriteBitNum = bufSize << 3;
  94   }
  95}
  96
  97
  98class HuffmanProcessor
  99{
 100   static const U32 csm_charFreqs[256];
 101   bool   m_tablesBuilt;
 102
 103   void buildTables();
 104
 105   struct HuffNode {
 106      U32 pop;
 107
 108      S16 index0;
 109      S16 index1;
 110   };
 111   struct HuffLeaf {
 112      U32 pop;
 113
 114      U8  numBits;
 115      U8  symbol;
 116      U32 code;   // no code should be longer than 32 bits.
 117   };
 118   // We have to be a bit careful with these, mSince they are pointers...
 119   struct HuffWrap {
 120      HuffNode* pNode;
 121      HuffLeaf* pLeaf;
 122
 123     public:
 124      HuffWrap() : pNode(NULL), pLeaf(NULL) { }
 125
 126      void set(HuffLeaf* in_leaf) { pNode = NULL; pLeaf = in_leaf; }
 127      void set(HuffNode* in_node) { pLeaf = NULL; pNode = in_node; }
 128
 129      U32 getPop() { if (pNode) return pNode->pop; else return pLeaf->pop; }
 130   };
 131
 132   Vector<HuffNode> m_huffNodes;
 133   Vector<HuffLeaf> m_huffLeaves;
 134
 135   S16 determineIndex(HuffWrap&);
 136
 137   void generateCodes(BitStream&, S32, S32);
 138
 139  public:
 140   HuffmanProcessor() : m_tablesBuilt(false) { }
 141
 142   static HuffmanProcessor g_huffProcessor;
 143
 144   bool readHuffBuffer(BitStream* pStream, char* out_pBuffer);
 145   bool writeHuffBuffer(BitStream* pStream, const char* out_pBuffer, S32 maxLen);
 146};
 147
 148HuffmanProcessor HuffmanProcessor::g_huffProcessor;
 149
 150void BitStream::setBuffer(void *bufPtr, S32 size, S32 maxSize)
 151{
 152   dataPtr = (U8 *) bufPtr;
 153   bitNum = 0;
 154   bufSize = size;
 155   maxReadBitNum = size << 3;
 156   if(maxSize < 0)
 157      maxSize = size;
 158   maxWriteBitNum = maxSize << 3;
 159   error = false;
 160   clearCompressionPoint();
 161}
 162
 163U32 BitStream::getPosition() const
 164{
 165   return (bitNum + 7) >> 3;
 166}
 167
 168
 169bool BitStream::setPosition(const U32 pos)
 170{
 171   bitNum = pos << 3;
 172   return (true);
 173}
 174
 175U32 BitStream::getStreamSize()
 176{
 177   return bufSize;
 178}
 179
 180U8 *BitStream::getBytePtr()
 181{
 182   return dataPtr + getPosition();
 183}
 184
 185
 186U32 BitStream::getReadByteSize()
 187{
 188   return (maxReadBitNum >> 3) - getPosition();
 189}
 190
 191U32 BitStream::getWriteByteSize()
 192{
 193   return (maxWriteBitNum >> 3) - getPosition();
 194}
 195
 196void BitStream::clear()
 197{
 198   dMemset(dataPtr, 0, bufSize);
 199}
 200
 201void BitStream::writeClassId(U32 classId, U32 classType, U32 classGroup)
 202{
 203   AssertFatal(classType < NetClassTypesCount, "Out of range class type.");
 204   AssertFatal(classGroup < NetClassGroupsCount, "Out of range class group.");
 205   AssertFatal(classId < AbstractClassRep::NetClassCount[classGroup][classType], "Out of range class id.");
 206   AssertFatal(AbstractClassRep::NetClassCount[classGroup][classType] < (1 << AbstractClassRep::NetClassBitSize[classGroup][classType]), 
 207      "NetClassBitSize too small!");
 208
 209   writeInt(classId, AbstractClassRep::NetClassBitSize[classGroup][classType]);
 210}
 211
 212S32 BitStream::readClassId(U32 classType, U32 classGroup)
 213{
 214   AssertFatal(classType < NetClassTypesCount, "Out of range class type.");
 215   AssertFatal(classGroup < NetClassGroupsCount, "Out of range class group.");
 216   AssertFatal(AbstractClassRep::NetClassCount[classGroup][classType] < (1 << AbstractClassRep::NetClassBitSize[classGroup][classType]), 
 217      "NetClassBitSize too small!");
 218
 219   S32 ret = readInt(AbstractClassRep::NetClassBitSize[classGroup][classType]);
 220
 221   AssertFatal(ret < AbstractClassRep::NetClassCount[classGroup][classType], "BitStream::readClassId - unexpected class ID!");
 222   if(ret >= AbstractClassRep::NetClassCount[classGroup][classType])
 223      return -1;
 224   return ret;
 225}
 226
 227void BitStream::writeBits(S32 bitCount, const void *bitPtr)
 228{
 229   if(!bitCount)
 230      return;
 231
 232   if(bitCount + bitNum > maxWriteBitNum)
 233   {
 234      error = true;
 235      AssertFatal(false, "Out of range write");
 236      return;
 237   }
 238
 239   // [tom, 8/17/2006] This is probably a lot lamer then it needs to be. However,
 240   // at least it doesnt clobber data or overrun the buffer like the old code did.
 241   const U8 *ptr = (U8 *)bitPtr;
 242
 243   for(S32 srcBitNum = 0;srcBitNum < bitCount;srcBitNum++)
 244   {
 245      if((*(ptr + (srcBitNum >> 3)) & (1 << (srcBitNum & 0x7))) != 0)
 246         *(dataPtr + (bitNum >> 3)) |= (1 << (bitNum & 0x7));
 247      else
 248         *(dataPtr + (bitNum >> 3)) &= ~(1 << (bitNum & 0x7));
 249      bitNum++;
 250   }
 251}
 252
 253void BitStream::setBit(S32 bitCount, bool set)
 254{
 255   if(set)
 256      *(dataPtr + (bitCount >> 3)) |= (1 << (bitCount & 0x7));
 257   else
 258      *(dataPtr + (bitCount >> 3)) &= ~(1 << (bitCount & 0x7));
 259}
 260
 261bool BitStream::testBit(S32 bitCount)
 262{
 263   return (*(dataPtr + (bitCount >> 3)) & (1 << (bitCount & 0x7))) != 0;
 264}
 265
 266bool BitStream::writeFlag(bool val)
 267{
 268   if(bitNum + 1 > maxWriteBitNum)
 269   {
 270      error = true;
 271      AssertFatal(false, "Out of range write");
 272      return false;
 273   }
 274   if(val)
 275      *(dataPtr + (bitNum >> 3)) |= (1 << (bitNum & 0x7));
 276   else
 277      *(dataPtr + (bitNum >> 3)) &= ~(1 << (bitNum & 0x7));
 278   bitNum++;
 279   return (val);
 280}
 281
 282void BitStream::readBits(S32 bitCount, void *bitPtr)
 283{
 284   if(!bitCount)
 285      return;
 286   if(bitCount + bitNum > maxReadBitNum)
 287   {
 288      error = true;
 289      //AssertFatal(false, "Out of range read");
 290      AssertWarn(false, "Out of range read");
 291      return;
 292   }
 293   U8 *stPtr = dataPtr + (bitNum >> 3);
 294   S32 byteCount = (bitCount + 7) >> 3;
 295
 296   U8 *ptr = (U8 *) bitPtr;
 297
 298   S32 downShift = bitNum & 0x7;
 299   S32 upShift = 8 - downShift;
 300
 301   U8 curB = *stPtr;
 302   const U8 *stEnd = dataPtr + bufSize;
 303   while(byteCount--)
 304   {
 305      stPtr++;
 306      U8 nextB = stPtr < stEnd ? *stPtr : 0;
 307      *ptr++ = (curB >> downShift) | (nextB << upShift);
 308      curB = nextB;
 309   }
 310
 311   bitNum += bitCount;
 312}
 313
 314bool BitStream::_read(U32 size, void *dataPtr)
 315{
 316   readBits(size << 3, dataPtr);
 317   return true;
 318}
 319
 320bool BitStream::_write(U32 size, const void *dataPtr)
 321{
 322   writeBits(size << 3, dataPtr);
 323   return true;
 324}
 325
 326S32 BitStream::readInt(S32 bitCount)
 327{
 328   S32 ret = 0;
 329   readBits(bitCount, &ret);
 330   ret = convertLEndianToHost(ret);
 331   if(bitCount == 32)
 332      return ret;
 333   else
 334      ret &= (1 << bitCount) - 1;
 335   return ret;
 336}
 337
 338void BitStream::writeInt(S32 val, S32 bitCount)
 339{
 340   AssertFatal((bitCount == 32) || ((val >> bitCount) == 0), avar("BitStream::writeInt: value out of range: %i/%i (%i bits)", val, 1 << bitCount, bitCount));
 341
 342   val = convertHostToLEndian(val);
 343   writeBits(bitCount, &val);
 344}
 345
 346void BitStream::writeFloat(F32 f, S32 bitCount)
 347{
 348   writeInt((S32)(f * ((1 << bitCount) - 1)), bitCount);
 349}
 350
 351F32 BitStream::readFloat(S32 bitCount)
 352{
 353   return readInt(bitCount) / F32((1 << bitCount) - 1);
 354}
 355
 356void BitStream::writeSignedFloat(F32 f, S32 bitCount)
 357{
 358   writeInt((S32)(((f + 1) * .5) * ((1 << bitCount) - 1)), bitCount);
 359}
 360
 361F32 BitStream::readSignedFloat(S32 bitCount)
 362{
 363   return readInt(bitCount) * 2 / F32((1 << bitCount) - 1) - 1.0f;
 364}
 365
 366void BitStream::writeSignedInt(S32 value, S32 bitCount)
 367{
 368   if(writeFlag(value < 0))
 369      writeInt(-value, bitCount - 1);
 370   else
 371      writeInt(value, bitCount - 1);
 372}
 373
 374S32 BitStream::readSignedInt(S32 bitCount)
 375{
 376   if(readFlag())
 377      return -readInt(bitCount - 1);
 378   else
 379      return readInt(bitCount - 1);
 380}
 381
 382void BitStream::writeNormalVector(const Point3F& vec, S32 bitCount)
 383{
 384   F32 phi   = mAtan2(vec.x, vec.y) / M_PI;
 385   F32 theta = mAtan2(vec.z, mSqrt(vec.x*vec.x + vec.y*vec.y)) / (M_PI/2.0);
 386
 387   writeSignedFloat(phi, bitCount+1);
 388   writeSignedFloat(theta, bitCount);
 389}
 390
 391void BitStream::readNormalVector(Point3F *vec, S32 bitCount)
 392{
 393   F32 phi   = readSignedFloat(bitCount+1) * M_PI;
 394   F32 theta = readSignedFloat(bitCount) * (M_PI/2.0);
 395
 396   vec->x = mSin(phi)*mCos(theta);
 397   vec->y = mCos(phi)*mCos(theta);
 398   vec->z = mSin(theta);
 399}
 400
 401Point3F BitStream::dumbDownNormal(const Point3F& vec, S32 bitCount)
 402{
 403   U8 buffer[128];
 404   BitStream temp(buffer, 128);
 405
 406   temp.writeNormalVector(vec, bitCount);
 407   temp.setCurPos(0);
 408
 409   Point3F ret;
 410   temp.readNormalVector(&ret, bitCount);
 411   return ret;
 412}
 413
 414void BitStream::writeVector( Point3F vec, F32 maxMag, S32 magBits, S32 normalBits )
 415{
 416   F32 mag = vec.len();
 417
 418   // If its zero length then we're done.
 419   if ( !writeFlag( mag > 0.0f ) )
 420      return;
 421
 422   // Write the magnitude compressed unless its greater than the maximum.
 423   if ( writeFlag( mag < maxMag ) )
 424      writeFloat( mag / maxMag, magBits );
 425   else
 426      write( mag );
 427
 428   // Finally write the normal part.
 429   vec *= 1.0f / mag;
 430   writeNormalVector( vec, normalBits );
 431}
 432
 433void BitStream::readVector( Point3F *outVec, F32 maxMag, S32 magBits, S32 normalBits )
 434{
 435   // Nothing more to do if we got a zero length vector.
 436   if ( !readFlag() )
 437   {
 438      outVec->set(0,0,0);
 439      return;
 440   }
 441
 442   // Read the compressed or uncompressed magnitude.
 443   F32 mag;
 444   if ( readFlag() )
 445      mag = readFloat( magBits ) * maxMag;
 446   else
 447      read( &mag );
 448
 449   // Finally read the normal and reconstruct the vector.
 450   readNormalVector( outVec, normalBits );
 451   *outVec *= mag;
 452}
 453
 454void BitStream::writeAffineTransform(const MatrixF& matrix)
 455{
 456//   AssertFatal(matrix.isAffine() == true,
 457//               "BitStream::writeAffineTransform: Error, must write only affine transforms!");
 458
 459   Point3F pos;
 460   matrix.getColumn(3, &pos);
 461   mathWrite(*this, pos);
 462
 463   QuatF q(matrix);
 464   q.normalize();
 465   write(q.x);
 466   write(q.y);
 467   write(q.z);
 468   writeFlag(q.w < 0.0);
 469}
 470
 471void BitStream::readAffineTransform(MatrixF* matrix)
 472{
 473   Point3F pos;
 474   QuatF   q;
 475
 476   mathRead(*this, &pos);
 477   read(&q.x);
 478   read(&q.y);
 479   read(&q.z);
 480   q.w = mSqrt(1.0 - getMin(F32(((q.x * q.x) + (q.y * q.y) + (q.z * q.z))), 1.f));
 481   if (readFlag())
 482      q.w = -q.w;
 483
 484   q.setMatrix(matrix);
 485   matrix->setColumn(3, pos);
 486//   AssertFatal(matrix->isAffine() == true,
 487//               "BitStream::readAffineTransform: Error, transform should be affine after this function!");
 488}
 489
 490void BitStream::writeQuat( const QuatF& quat, U32 bitCount )
 491{
 492   writeSignedFloat( quat.x, bitCount );
 493   writeSignedFloat( quat.y, bitCount );
 494   writeSignedFloat( quat.z, bitCount );
 495   writeFlag( quat.w < 0.0f );
 496}
 497
 498void BitStream::readQuat( QuatF *outQuat, U32 bitCount )
 499{
 500   outQuat->x = readSignedFloat( bitCount );
 501   outQuat->y = readSignedFloat( bitCount );
 502   outQuat->z = readSignedFloat( bitCount );
 503
 504   outQuat->w = mSqrt( 1.0 - getMin(   mSquared( outQuat->x ) + 
 505                                       mSquared( outQuat->y ) + 
 506                                       mSquared( outQuat->z ),
 507                                       1.0f ) );
 508   if ( readFlag() )
 509      outQuat->w = -outQuat->w;
 510}
 511
 512void BitStream::writeBits( const BitVector &bitvec )
 513{
 514   U32 size = bitvec.getSize();   
 515   if ( writeFlag( size <= 127 ) )
 516      writeInt( size, 7 );
 517   else
 518      write( size );
 519
 520   writeBits( bitvec.getSize(), bitvec.getBits() );
 521}
 522
 523void BitStream::readBits( BitVector *bitvec )
 524{
 525   U32 size;   
 526   if ( readFlag() ) // size <= 127
 527      size = readInt( 7 );
 528   else
 529      read( &size );
 530
 531   bitvec->setSize( size );
 532   readBits( size, bitvec->getBits() );
 533}
 534
 535//----------------------------------------------------------------------------
 536
 537void BitStream::clearCompressionPoint()
 538{
 539   mCompressPoint.set(0,0,0);
 540}
 541
 542void BitStream::setCompressionPoint(const Point3F& p)
 543{
 544   mCompressPoint = p;
 545}
 546
 547static U32 gBitCounts[4] = {
 548   16, 18, 20, 32
 549};
 550
 551void BitStream::writeCompressedPoint(const Point3F& p,F32 scale)
 552{
 553   // Same # of bits for all axis
 554   Point3F vec;
 555   F32 invScale = 1 / scale;
 556   U32 type;
 557   vec = p - mCompressPoint;
 558   F32 dist = vec.len() * invScale;
 559   if(dist < (1 << 15))
 560      type = 0;
 561   else if(dist < (1 << 17))
 562      type = 1;
 563   else if(dist < (1 << 19))
 564      type = 2;
 565   else
 566      type = 3;
 567
 568   writeInt(type, 2);
 569
 570   if (type != 3)
 571   {
 572      type = gBitCounts[type];
 573      writeSignedInt(S32(vec.x * invScale + 0.5f),type);
 574      writeSignedInt(S32(vec.y * invScale + 0.5f),type);
 575      writeSignedInt(S32(vec.z * invScale + 0.5f),type);
 576   }
 577   else
 578   {
 579      write(p.x);
 580      write(p.y);
 581      write(p.z);
 582   }
 583}
 584
 585void BitStream::readCompressedPoint(Point3F* p,F32 scale)
 586{
 587   // Same # of bits for all axis
 588   U32 type = readInt(2);
 589
 590   if(type == 3)
 591   {
 592      read(&p->x);
 593      read(&p->y);
 594      read(&p->z);
 595   }
 596   else
 597   {
 598      type = gBitCounts[type];
 599      p->x = (F32)readSignedInt(type);
 600      p->y = (F32)readSignedInt(type);
 601      p->z = (F32)readSignedInt(type);
 602
 603      p->x = mCompressPoint.x + p->x * scale;
 604      p->y = mCompressPoint.y + p->y * scale;
 605      p->z = mCompressPoint.z + p->z * scale;
 606   }
 607}
 608
 609//------------------------------------------------------------------------------
 610
 611InfiniteBitStream::InfiniteBitStream()
 612{
 613   //
 614}
 615
 616InfiniteBitStream::~InfiniteBitStream()
 617{
 618   //
 619}
 620
 621void InfiniteBitStream::reset()
 622{
 623   // Rewing back to beginning
 624   setPosition(0);
 625}
 626
 627void InfiniteBitStream::validate(U32 upcomingBytes)
 628{
 629   if(getPosition() + upcomingBytes + mMinSpace > bufSize)
 630   {
 631      bufSize = getPosition() + upcomingBytes + mMinSpace;
 632      dataPtr = (U8 *) dRealloc(dataPtr, bufSize);
 633
 634      maxReadBitNum = bufSize << 3;
 635      maxWriteBitNum = bufSize << 3;
 636   }
 637}
 638
 639void InfiniteBitStream::compact()
 640{
 641   // Prepare to copy...
 642   U32 oldSize = bufSize;
 643   U8 *tmp = (U8*)dMalloc(bufSize);
 644
 645   // Copy things...
 646   bufSize = getPosition() + mMinSpace * 2;
 647   dMemcpy(tmp, dataPtr, oldSize);
 648
 649   // And clean up.
 650   dFree(dataPtr);
 651   dataPtr = tmp;
 652
 653   maxReadBitNum = bufSize << 3;
 654   maxWriteBitNum = bufSize << 3;
 655}
 656
 657void InfiniteBitStream::writeToStream(Stream &s)
 658{
 659   s.write(getPosition(), dataPtr);
 660}
 661
 662//------------------------------------------------------------------------------
 663
 664void BitStream::readString(char buf[256])
 665{
 666   if(stringBuffer)
 667   {
 668      if(readFlag())
 669      {
 670         S32 offset = readInt(8);
 671         HuffmanProcessor::g_huffProcessor.readHuffBuffer(this, stringBuffer + offset);
 672         dStrcpy(buf, stringBuffer);
 673         return;
 674      }
 675   }
 676   HuffmanProcessor::g_huffProcessor.readHuffBuffer(this, buf);
 677   if(stringBuffer)
 678      dStrcpy(stringBuffer, buf);
 679}
 680
 681void BitStream::writeString(const char *string, S32 maxLen)
 682{
 683   if(!string)
 684      string = "";
 685   if(stringBuffer)
 686   {
 687      S32 j;
 688      for(j = 0; j < maxLen && stringBuffer[j] == string[j] && string[j];j++)
 689         ;
 690      dStrncpy(stringBuffer, string, maxLen);
 691      stringBuffer[maxLen] = 0;
 692
 693      if(writeFlag(j > 2))
 694      {
 695         writeInt(j, 8);
 696         HuffmanProcessor::g_huffProcessor.writeHuffBuffer(this, string + j, maxLen - j);
 697         return;
 698      }
 699   }
 700   HuffmanProcessor::g_huffProcessor.writeHuffBuffer(this, string, maxLen);
 701}
 702
 703void HuffmanProcessor::buildTables()
 704{
 705   AssertFatal(m_tablesBuilt == false, "Cannot build tables twice!");
 706   m_tablesBuilt = true;
 707
 708   S32 i;
 709
 710   // First, construct the array of wraps...
 711   //
 712   m_huffLeaves.setSize(256);
 713   m_huffNodes.reserve(256);
 714   m_huffNodes.increment();
 715   for (i = 0; i < 256; i++) {
 716      HuffLeaf& rLeaf = m_huffLeaves[i];
 717
 718      rLeaf.pop    = csm_charFreqs[i] + 1;
 719      rLeaf.symbol = U8(i);
 720
 721      dMemset(&rLeaf.code, 0, sizeof(rLeaf.code));
 722      rLeaf.numBits = 0;
 723   }
 724
 725   S32 currWraps = 256;
 726   HuffWrap* pWrap = new HuffWrap[256];
 727   for (i = 0; i < 256; i++) {
 728      pWrap[i].set(&m_huffLeaves[i]);
 729   }
 730
 731   while (currWraps != 1) {
 732      U32 min1 = 0xfffffffe, min2 = 0xffffffff;
 733      S32 index1 = -1, index2 = -1;
 734
 735      for (i = 0; i < currWraps; i++) {
 736         if (pWrap[i].getPop() < min1) {
 737            min2   = min1;
 738            index2 = index1;
 739
 740            min1   = pWrap[i].getPop();
 741            index1 = i;
 742         } else if (pWrap[i].getPop() < min2) {
 743            min2   = pWrap[i].getPop();
 744            index2 = i;
 745         }
 746      }
 747      AssertFatal(index1 != -1 && index2 != -1 && index1 != index2, "hrph");
 748
 749      // Create a node for this...
 750      m_huffNodes.increment();
 751      HuffNode& rNode = m_huffNodes.last();
 752      rNode.pop    = pWrap[index1].getPop() + pWrap[index2].getPop();
 753      rNode.index0 = determineIndex(pWrap[index1]);
 754      rNode.index1 = determineIndex(pWrap[index2]);
 755
 756      S32 mergeIndex = index1 > index2 ? index2 : index1;
 757      S32 nukeIndex  = index1 > index2 ? index1 : index2;
 758      pWrap[mergeIndex].set(&rNode);
 759
 760      if (index2 != (currWraps - 1)) {
 761         pWrap[nukeIndex] = pWrap[currWraps - 1];
 762      }
 763      currWraps--;
 764   }
 765   AssertFatal(currWraps == 1, "wrong wraps?");
 766   AssertFatal(pWrap[0].pNode != NULL && pWrap[0].pLeaf == NULL, "Wrong wrap type!");
 767
 768   // Ok, now we have one wrap, which is a node.  we need to make sure that this
 769   //  is the first node in the node list.
 770   m_huffNodes[0] = *(pWrap[0].pNode);
 771   delete [] pWrap;
 772
 773   U32 code = 0;
 774   BitStream bs(&code, 4);
 775
 776   generateCodes(bs, 0, 0);
 777}
 778
 779void HuffmanProcessor::generateCodes(BitStream& rBS, S32 index, S32 depth)
 780{
 781   if (index < 0) {
 782      // leaf node, copy the code in, and back out...
 783      HuffLeaf& rLeaf = m_huffLeaves[-(index + 1)];
 784
 785      dMemcpy(&rLeaf.code, rBS.dataPtr, sizeof(rLeaf.code));
 786      rLeaf.numBits = depth;
 787   } else {
 788      HuffNode& rNode = m_huffNodes[index];
 789
 790      S32 pos = rBS.getCurPos();
 791
 792      rBS.writeFlag(false);
 793      generateCodes(rBS, rNode.index0, depth + 1);
 794
 795      rBS.setCurPos(pos);
 796      rBS.writeFlag(true);
 797      generateCodes(rBS, rNode.index1, depth + 1);
 798
 799      rBS.setCurPos(pos);
 800   }
 801}
 802
 803S16 HuffmanProcessor::determineIndex(HuffWrap& rWrap)
 804{
 805   if (rWrap.pLeaf != NULL) {
 806      AssertFatal(rWrap.pNode == NULL, "Got a non-NULL pNode in a HuffWrap with a non-NULL leaf.");
 807
 808      return -((rWrap.pLeaf - m_huffLeaves.address()) + 1);
 809   } else {
 810      AssertFatal(rWrap.pNode != NULL, "Got a NULL pNode in a HuffWrap with a NULL leaf.");
 811
 812      return rWrap.pNode - m_huffNodes.address();
 813   }
 814}
 815
 816bool HuffmanProcessor::readHuffBuffer(BitStream* pStream, char* out_pBuffer)
 817{
 818   if (m_tablesBuilt == false)
 819      buildTables();
 820
 821   if (pStream->readFlag()) {
 822      S32 len = pStream->readInt(8);
 823      for (S32 i = 0; i < len; i++) {
 824         S32 index = 0;
 825         while (true) {
 826            if (index >= 0) {
 827               if (pStream->readFlag() == true) {
 828                  index = m_huffNodes[index].index1;
 829               } else {
 830                  index = m_huffNodes[index].index0;
 831               }
 832            } else {
 833               out_pBuffer[i] = m_huffLeaves[-(index+1)].symbol;
 834               break;
 835            }
 836         }
 837      }
 838      out_pBuffer[len] = '\0';
 839      return true;
 840   } else {
 841      // Uncompressed string...
 842      U32 len = pStream->readInt(8);
 843      pStream->read(len, out_pBuffer);
 844      out_pBuffer[len] = '\0';
 845      return true;
 846   }
 847}
 848
 849bool HuffmanProcessor::writeHuffBuffer(BitStream* pStream, const char* out_pBuffer, S32 maxLen)
 850{
 851   if (out_pBuffer == NULL) {
 852      pStream->writeFlag(false);
 853      pStream->writeInt(0, 8);
 854      return true;
 855   }
 856
 857   if (m_tablesBuilt == false)
 858      buildTables();
 859
 860   S32 len = out_pBuffer ? dStrlen(out_pBuffer) : 0;
 861   AssertWarn(len <= 255, "String TOO long for writeString");
 862   AssertWarn(len <= 255, out_pBuffer);
 863   if (len > maxLen)
 864      len = maxLen;
 865
 866   S32 numBits = 0;
 867   S32 i;
 868   for (i = 0; i < len; i++)
 869      numBits += m_huffLeaves[(unsigned char)out_pBuffer[i]].numBits;
 870
 871   if (numBits >= (len * 8)) {
 872      pStream->writeFlag(false);
 873      pStream->writeInt(len, 8);
 874      pStream->write(len, out_pBuffer);
 875   } else {
 876      pStream->writeFlag(true);
 877      pStream->writeInt(len, 8);
 878      for (i = 0; i < len; i++) {
 879         HuffLeaf& rLeaf = m_huffLeaves[((unsigned char)out_pBuffer[i])];
 880         pStream->writeBits(rLeaf.numBits, &rLeaf.code);
 881      }
 882   }
 883
 884   return true;
 885}
 886
 887const U32 HuffmanProcessor::csm_charFreqs[256] = {
 8880     ,
 8890     ,
 8900     ,
 8910     ,
 8920     ,
 8930     ,
 8940     ,
 8950     ,
 8960     ,
 897329   ,
 89821    ,
 8990     ,
 9000     ,
 9010     ,
 9020     ,
 9030     ,
 9040     ,
 9050     ,
 9060     ,
 9070     ,
 9080     ,
 9090     ,
 9100     ,
 9110     ,
 9120     ,
 9130     ,
 9140     ,
 9150     ,
 9160     ,
 9170     ,
 9180     ,
 9190     ,
 9202809  ,
 92168    ,
 9220     ,
 92327    ,
 9240     ,
 92558    ,
 9263     ,
 92762    ,
 9284     ,
 9297     ,
 9300     ,
 9310     ,
 93215    ,
 93365    ,
 934554   ,
 9353     ,
 936394   ,
 937404   ,
 938189   ,
 939117   ,
 94030    ,
 94151    ,
 94227    ,
 94315    ,
 94434    ,
 94532    ,
 94680    ,
 9471     ,
 948142   ,
 9493     ,
 950142   ,
 95139    ,
 9520     ,
 953144   ,
 954125   ,
 95544    ,
 956122   ,
 957275   ,
 95870    ,
 959135   ,
 96061    ,
 961127   ,
 9628     ,
 96312    ,
 964113   ,
 965246   ,
 966122   ,
 96736    ,
 968185   ,
 9691     ,
 970149   ,
 971309   ,
 972335   ,
 97312    ,
 97411    ,
 97514    ,
 97654    ,
 977151   ,
 9780     ,
 9790     ,
 9802     ,
 9810     ,
 9820     ,
 983211   ,
 9840     ,
 9852090  ,
 986344   ,
 987736   ,
 988993   ,
 9892872  ,
 990701   ,
 991605   ,
 992646   ,
 9931552  ,
 994328   ,
 995305   ,
 9961240  ,
 997735   ,
 9981533  ,
 9991713  ,
1000562   ,
10013     ,
10021775  ,
10031149  ,
10041469  ,
1005979   ,
1006407   ,
1007553   ,
100859    ,
1009279   ,
101031    ,
10110     ,
10120     ,
10130     ,
101468    ,
10150     ,
10160     ,
10170     ,
10180     ,
10190     ,
10200     ,
10210     ,
10220     ,
10230     ,
10240     ,
10250     ,
10260     ,
10270     ,
10280     ,
10290     ,
10300     ,
10310     ,
10320     ,
10330     ,
10340     ,
10350     ,
10360     ,
10370     ,
10380     ,
10390     ,
10400     ,
10410     ,
10420     ,
10430     ,
10440     ,
10450     ,
10460     ,
10470     ,
10480     ,
10490     ,
10500     ,
10510     ,
10520     ,
10530     ,
10540     ,
10550     ,
10560     ,
10570     ,
10580     ,
10590     ,
10600     ,
10610     ,
10620     ,
10630     ,
10640     ,
10650     ,
10660     ,
10670     ,
10680     ,
10690     ,
10700     ,
10710     ,
10720     ,
10730     ,
10740     ,
10750     ,
10760     ,
10770     ,
10780     ,
10790     ,
10800     ,
10810     ,
10820     ,
10830     ,
10840     ,
10850     ,
10860     ,
10870     ,
10880     ,
10890     ,
10900     ,
10910     ,
10920     ,
10930     ,
10940     ,
10950     ,
10960     ,
10970     ,
10980     ,
10990     ,
11000     ,
11010     ,
11020     ,
11030     ,
11040     ,
11050     ,
11060     ,
11070     ,
11080     ,
11090     ,
11100     ,
11110     ,
11120     ,
11130     ,
11140     ,
11150     ,
11160     ,
11170     ,
11180     ,
11190     ,
11200     ,
11210     ,
11220     ,
11230     ,
11240     ,
11250     ,
11260     ,
11270     ,
11280     ,
11290     ,
11300     ,
11310     ,
11320     ,
11330     ,
11340     ,
11350     ,
11360     ,
11370     ,
11380     ,
11390     ,
11400     ,
11410     ,
11420     ,
11430
1144};
1145
1146