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(mDataPtr);
  83}
  84
  85void ResizeBitStream::validate()
  86{
  87   if(getPosition() + mMinSpace > bufSize)
  88   {
  89      bufSize = getPosition() + mMinSpace * 2;
  90     mDataPtr = (U8 *) dRealloc(mDataPtr, 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, S32 maxLen);
 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   mDataPtr = (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 mDataPtr + 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(mDataPtr, 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         *(mDataPtr + (bitNum >> 3)) |= (1 << (bitNum & 0x7));
 247      else
 248         *(mDataPtr + (bitNum >> 3)) &= ~(1 << (bitNum & 0x7));
 249      bitNum++;
 250   }
 251}
 252
 253void BitStream::setBit(S32 bitCount, bool set)
 254{
 255   if(set)
 256      *(mDataPtr + (bitCount >> 3)) |= (1 << (bitCount & 0x7));
 257   else
 258      *(mDataPtr + (bitCount >> 3)) &= ~(1 << (bitCount & 0x7));
 259}
 260
 261bool BitStream::testBit(S32 bitCount)
 262{
 263   return (*(mDataPtr + (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      *(mDataPtr + (bitNum >> 3)) |= (1 << (bitNum & 0x7));
 276   else
 277      *(mDataPtr + (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 = mDataPtr + (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 = mDataPtr + 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   F32 quatVals[4] = { quat.x, quat.y, quat.z, quat.w };
 493   bool flipQuat = (quatVals[0] < 0);
 494   F32 maxVal = mFabs(quatVals[0]);
 495   S32 idxMax = 0;
 496
 497   for (S32 i = 1; i < 4; ++i)
 498   {
 499      if (mFabs(quatVals[i]) > maxVal)
 500      {
 501         idxMax = i;
 502         maxVal = mFabs(quatVals[i]);
 503         flipQuat = (quatVals[i] < 0);
 504      }
 505   }
 506   writeInt(idxMax, 2);
 507
 508   for (S32 i = 0; i < 4; ++i)
 509   {
 510      if (i == idxMax)
 511         continue;
 512      F32 curValue = (flipQuat ? -quatVals[i] : quatVals[i]) * (F32) M_SQRT2;
 513      writeSignedFloat( curValue, bitCount );
 514   }
 515}
 516
 517void BitStream::readQuat( QuatF *outQuat, U32 bitCount )
 518{
 519   F32 quatVals[4];
 520   F32 sum = 0.0f;
 521
 522   S32 idxMax = readInt( 2 );
 523   for (S32 i = 0; i < 4; ++i)
 524   {
 525      if (i == idxMax)
 526         continue;
 527      quatVals[i] = readSignedFloat( bitCount ) * M_SQRTHALF_F;
 528      sum += quatVals[i] * quatVals[i];
 529   }
 530
 531   if (sum > 1.0f)
 532      quatVals[idxMax] = 1.0f;
 533   else
 534      quatVals[idxMax] = mSqrt(1.0f - sum);
 535
 536   outQuat->set(quatVals[0], quatVals[1], quatVals[2], quatVals[3]);
 537}
 538
 539void BitStream::writeBits( const BitVector &bitvec )
 540{
 541   U32 size = bitvec.getSize();   
 542   if ( writeFlag( size <= 127 ) )
 543      writeInt( size, 7 );
 544   else
 545      write( size );
 546
 547   writeBits( bitvec.getSize(), bitvec.getBits() );
 548}
 549
 550void BitStream::readBits( BitVector *bitvec )
 551{
 552   U32 size;   
 553   if ( readFlag() ) // size <= 127
 554      size = readInt( 7 );
 555   else
 556      read( &size );
 557
 558   bitvec->setSize( size );
 559   readBits( size, bitvec->getBits() );
 560}
 561
 562//----------------------------------------------------------------------------
 563
 564void BitStream::clearCompressionPoint()
 565{
 566   mCompressPoint.set(0,0,0);
 567}
 568
 569void BitStream::setCompressionPoint(const Point3F& p)
 570{
 571   mCompressPoint = p;
 572}
 573
 574static U32 gBitCounts[4] = {
 575   16, 18, 20, 32
 576};
 577
 578void BitStream::writeCompressedPoint(const Point3F& p,F32 scale)
 579{
 580   // Same # of bits for all axis
 581   Point3F vec;
 582   F32 invScale = 1 / scale;
 583   U32 type;
 584   vec = p - mCompressPoint;
 585   F32 dist = vec.len() * invScale;
 586   if(dist < (1 << 15))
 587      type = 0;
 588   else if(dist < (1 << 17))
 589      type = 1;
 590   else if(dist < (1 << 19))
 591      type = 2;
 592   else
 593      type = 3;
 594
 595   writeInt(type, 2);
 596
 597   if (type != 3)
 598   {
 599      type = gBitCounts[type];
 600      writeSignedInt(S32(vec.x * invScale + 0.5f),type);
 601      writeSignedInt(S32(vec.y * invScale + 0.5f),type);
 602      writeSignedInt(S32(vec.z * invScale + 0.5f),type);
 603   }
 604   else
 605   {
 606      write(p.x);
 607      write(p.y);
 608      write(p.z);
 609   }
 610}
 611
 612void BitStream::readCompressedPoint(Point3F* p,F32 scale)
 613{
 614   // Same # of bits for all axis
 615   U32 type = readInt(2);
 616
 617   if(type == 3)
 618   {
 619      read(&p->x);
 620      read(&p->y);
 621      read(&p->z);
 622   }
 623   else
 624   {
 625      type = gBitCounts[type];
 626      p->x = (F32)readSignedInt(type);
 627      p->y = (F32)readSignedInt(type);
 628      p->z = (F32)readSignedInt(type);
 629
 630      p->x = mCompressPoint.x + p->x * scale;
 631      p->y = mCompressPoint.y + p->y * scale;
 632      p->z = mCompressPoint.z + p->z * scale;
 633   }
 634}
 635
 636//------------------------------------------------------------------------------
 637
 638InfiniteBitStream::InfiniteBitStream()
 639{
 640   //
 641}
 642
 643InfiniteBitStream::~InfiniteBitStream()
 644{
 645   //
 646}
 647
 648void InfiniteBitStream::reset()
 649{
 650   // Rewing back to beginning
 651   setPosition(0);
 652}
 653
 654void InfiniteBitStream::validate(U32 upcomingBytes)
 655{
 656   if(getPosition() + upcomingBytes + mMinSpace > bufSize)
 657   {
 658      bufSize = getPosition() + upcomingBytes + mMinSpace;
 659     mDataPtr = (U8 *) dRealloc(mDataPtr, bufSize);
 660
 661      maxReadBitNum = bufSize << 3;
 662      maxWriteBitNum = bufSize << 3;
 663   }
 664}
 665
 666void InfiniteBitStream::compact()
 667{
 668   // Prepare to copy...
 669   U32 oldSize = bufSize;
 670   U8 *tmp = (U8*)dMalloc(bufSize);
 671
 672   // Copy things...
 673   bufSize = getPosition() + mMinSpace * 2;
 674   dMemcpy(tmp, mDataPtr, oldSize);
 675
 676   // And clean up.
 677   dFree(mDataPtr);
 678   mDataPtr = tmp;
 679
 680   maxReadBitNum = bufSize << 3;
 681   maxWriteBitNum = bufSize << 3;
 682}
 683
 684void InfiniteBitStream::writeToStream(Stream &s)
 685{
 686   s.write(getPosition(), mDataPtr);
 687}
 688
 689//------------------------------------------------------------------------------
 690
 691void BitStream::readString(char buf[256])
 692{
 693   if(stringBuffer)
 694   {
 695      if(readFlag())
 696      {
 697         S32 offset = readInt(8);
 698         HuffmanProcessor::g_huffProcessor.readHuffBuffer(this, stringBuffer + offset, 256 - offset);
 699         dStrcpy(buf, stringBuffer, 256);
 700         return;
 701      }
 702   }
 703   HuffmanProcessor::g_huffProcessor.readHuffBuffer(this, buf, 256);
 704   if(stringBuffer)
 705      dStrcpy(stringBuffer, buf, 256);
 706}
 707
 708void BitStream::writeString(const char *string, S32 maxLen)
 709{
 710   if(!string)
 711      string = "";
 712   if(stringBuffer)
 713   {
 714      S32 j;
 715      for(j = 0; j < maxLen && stringBuffer[j] == string[j] && string[j];j++)
 716         ;
 717      dStrncpy(stringBuffer, string, maxLen);
 718      stringBuffer[maxLen] = 0;
 719
 720      if(writeFlag(j > 2))
 721      {
 722         writeInt(j, 8);
 723         HuffmanProcessor::g_huffProcessor.writeHuffBuffer(this, string + j, maxLen - j);
 724         return;
 725      }
 726   }
 727   HuffmanProcessor::g_huffProcessor.writeHuffBuffer(this, string, maxLen);
 728}
 729
 730void HuffmanProcessor::buildTables()
 731{
 732   AssertFatal(m_tablesBuilt == false, "Cannot build tables twice!");
 733   m_tablesBuilt = true;
 734
 735   S32 i;
 736
 737   // First, construct the array of wraps...
 738   //
 739   m_huffLeaves.setSize(256);
 740   m_huffNodes.reserve(256);
 741   m_huffNodes.increment();
 742   for (i = 0; i < 256; i++) {
 743      HuffLeaf& rLeaf = m_huffLeaves[i];
 744
 745      rLeaf.pop    = csm_charFreqs[i] + 1;
 746      rLeaf.symbol = U8(i);
 747
 748      dMemset(&rLeaf.code, 0, sizeof(rLeaf.code));
 749      rLeaf.numBits = 0;
 750   }
 751
 752   S32 currWraps = 256;
 753   HuffWrap* pWrap = new HuffWrap[256];
 754   for (i = 0; i < 256; i++) {
 755      pWrap[i].set(&m_huffLeaves[i]);
 756   }
 757
 758   while (currWraps != 1) {
 759      U32 min1 = 0xfffffffe, min2 = 0xffffffff;
 760      S32 index1 = -1, index2 = -1;
 761
 762      for (i = 0; i < currWraps; i++) {
 763         if (pWrap[i].getPop() < min1) {
 764            min2   = min1;
 765            index2 = index1;
 766
 767            min1   = pWrap[i].getPop();
 768            index1 = i;
 769         } else if (pWrap[i].getPop() < min2) {
 770            min2   = pWrap[i].getPop();
 771            index2 = i;
 772         }
 773      }
 774      AssertFatal(index1 != -1 && index2 != -1 && index1 != index2, "hrph");
 775
 776      // Create a node for this...
 777      m_huffNodes.increment();
 778      HuffNode& rNode = m_huffNodes.last();
 779      rNode.pop    = pWrap[index1].getPop() + pWrap[index2].getPop();
 780      rNode.index0 = determineIndex(pWrap[index1]);
 781      rNode.index1 = determineIndex(pWrap[index2]);
 782
 783      S32 mergeIndex = index1 > index2 ? index2 : index1;
 784      S32 nukeIndex  = index1 > index2 ? index1 : index2;
 785      pWrap[mergeIndex].set(&rNode);
 786
 787      if (index2 != (currWraps - 1)) {
 788         pWrap[nukeIndex] = pWrap[currWraps - 1];
 789      }
 790      currWraps--;
 791   }
 792   AssertFatal(currWraps == 1, "wrong wraps?");
 793   AssertFatal(pWrap[0].pNode != NULL && pWrap[0].pLeaf == NULL, "Wrong wrap type!");
 794
 795   // Ok, now we have one wrap, which is a node.  we need to make sure that this
 796   //  is the first node in the node list.
 797   m_huffNodes[0] = *(pWrap[0].pNode);
 798   delete [] pWrap;
 799
 800   U32 code = 0;
 801   BitStream bs(&code, 4);
 802
 803   generateCodes(bs, 0, 0);
 804}
 805
 806void HuffmanProcessor::generateCodes(BitStream& rBS, S32 index, S32 depth)
 807{
 808   if (index < 0) {
 809      // leaf node, copy the code in, and back out...
 810      HuffLeaf& rLeaf = m_huffLeaves[-(index + 1)];
 811
 812      dMemcpy(&rLeaf.code, rBS.mDataPtr, sizeof(rLeaf.code));
 813      rLeaf.numBits = depth;
 814   } else {
 815      HuffNode& rNode = m_huffNodes[index];
 816
 817      S32 pos = rBS.getCurPos();
 818
 819      rBS.writeFlag(false);
 820      generateCodes(rBS, rNode.index0, depth + 1);
 821
 822      rBS.setCurPos(pos);
 823      rBS.writeFlag(true);
 824      generateCodes(rBS, rNode.index1, depth + 1);
 825
 826      rBS.setCurPos(pos);
 827   }
 828}
 829
 830S16 HuffmanProcessor::determineIndex(HuffWrap& rWrap)
 831{
 832   if (rWrap.pLeaf != NULL) {
 833      AssertFatal(rWrap.pNode == NULL, "Got a non-NULL pNode in a HuffWrap with a non-NULL leaf.");
 834
 835      return -((rWrap.pLeaf - m_huffLeaves.address()) + 1);
 836   } else {
 837      AssertFatal(rWrap.pNode != NULL, "Got a NULL pNode in a HuffWrap with a NULL leaf.");
 838
 839      return rWrap.pNode - m_huffNodes.address();
 840   }
 841}
 842
 843bool HuffmanProcessor::readHuffBuffer(BitStream* pStream, char* out_pBuffer, S32 maxLen=256)
 844{
 845   if (m_tablesBuilt == false)
 846      buildTables();
 847
 848   if (pStream->readFlag()) {
 849      S32 len = pStream->readInt(8);
 850      if (len >= maxLen) {
 851         len = maxLen;
 852      }
 853      for (S32 i = 0; i < len; i++) {
 854         S32 index = 0;
 855         while (true) {
 856            if (index >= 0) {
 857               if (pStream->readFlag() == true) {
 858                  index = m_huffNodes[index].index1;
 859               } else {
 860                  index = m_huffNodes[index].index0;
 861               }
 862            } else {
 863               out_pBuffer[i] = m_huffLeaves[-(index+1)].symbol;
 864               break;
 865            }
 866         }
 867      }
 868      out_pBuffer[len] = '\0';
 869      return true;
 870   } else {
 871      // Uncompressed string...
 872      U32 len = pStream->readInt(8);
 873      if (len >= maxLen) {
 874         len = maxLen;
 875      }
 876      pStream->read(len, out_pBuffer);
 877      out_pBuffer[len] = '\0';
 878      return true;
 879   }
 880}
 881
 882bool HuffmanProcessor::writeHuffBuffer(BitStream* pStream, const char* out_pBuffer, S32 maxLen)
 883{
 884   if (out_pBuffer == NULL) {
 885      pStream->writeFlag(false);
 886      pStream->writeInt(0, 8);
 887      return true;
 888   }
 889
 890   if (m_tablesBuilt == false)
 891      buildTables();
 892
 893   S32 len = out_pBuffer ? dStrlen(out_pBuffer) : 0;
 894   AssertWarn(len <= 255, "String TOO long for writeString");
 895   AssertWarn(len <= 255, out_pBuffer);
 896   if (len > maxLen)
 897      len = maxLen;
 898
 899   S32 numBits = 0;
 900   S32 i;
 901   for (i = 0; i < len; i++)
 902      numBits += m_huffLeaves[(unsigned char)out_pBuffer[i]].numBits;
 903
 904   if (numBits >= (len * 8)) {
 905      pStream->writeFlag(false);
 906      pStream->writeInt(len, 8);
 907      pStream->write(len, out_pBuffer);
 908   } else {
 909      pStream->writeFlag(true);
 910      pStream->writeInt(len, 8);
 911      for (i = 0; i < len; i++) {
 912         HuffLeaf& rLeaf = m_huffLeaves[((unsigned char)out_pBuffer[i])];
 913         pStream->writeBits(rLeaf.numBits, &rLeaf.code);
 914      }
 915   }
 916
 917   return true;
 918}
 919
 920const U32 HuffmanProcessor::csm_charFreqs[256] = {
 9210     ,
 9220     ,
 9230     ,
 9240     ,
 9250     ,
 9260     ,
 9270     ,
 9280     ,
 9290     ,
 930329   ,
 93121    ,
 9320     ,
 9330     ,
 9340     ,
 9350     ,
 9360     ,
 9370     ,
 9380     ,
 9390     ,
 9400     ,
 9410     ,
 9420     ,
 9430     ,
 9440     ,
 9450     ,
 9460     ,
 9470     ,
 9480     ,
 9490     ,
 9500     ,
 9510     ,
 9520     ,
 9532809  ,
 95468    ,
 9550     ,
 95627    ,
 9570     ,
 95858    ,
 9593     ,
 96062    ,
 9614     ,
 9627     ,
 9630     ,
 9640     ,
 96515    ,
 96665    ,
 967554   ,
 9683     ,
 969394   ,
 970404   ,
 971189   ,
 972117   ,
 97330    ,
 97451    ,
 97527    ,
 97615    ,
 97734    ,
 97832    ,
 97980    ,
 9801     ,
 981142   ,
 9823     ,
 983142   ,
 98439    ,
 9850     ,
 986144   ,
 987125   ,
 98844    ,
 989122   ,
 990275   ,
 99170    ,
 992135   ,
 99361    ,
 994127   ,
 9958     ,
 99612    ,
 997113   ,
 998246   ,
 999122   ,
100036    ,
1001185   ,
10021     ,
1003149   ,
1004309   ,
1005335   ,
100612    ,
100711    ,
100814    ,
100954    ,
1010151   ,
10110     ,
10120     ,
10132     ,
10140     ,
10150     ,
1016211   ,
10170     ,
10182090  ,
1019344   ,
1020736   ,
1021993   ,
10222872  ,
1023701   ,
1024605   ,
1025646   ,
10261552  ,
1027328   ,
1028305   ,
10291240  ,
1030735   ,
10311533  ,
10321713  ,
1033562   ,
10343     ,
10351775  ,
10361149  ,
10371469  ,
1038979   ,
1039407   ,
1040553   ,
104159    ,
1042279   ,
104331    ,
10440     ,
10450     ,
10460     ,
104768    ,
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     ,
11440     ,
11450     ,
11460     ,
11470     ,
11480     ,
11490     ,
11500     ,
11510     ,
11520     ,
11530     ,
11540     ,
11550     ,
11560     ,
11570     ,
11580     ,
11590     ,
11600     ,
11610     ,
11620     ,
11630     ,
11640     ,
11650     ,
11660     ,
11670     ,
11680     ,
11690     ,
11700     ,
11710     ,
11720     ,
11730     ,
11740     ,
11750     ,
11760
1177};
1178
1179