1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/win32/7zip/7z/CPP/7zip/Compress/ImplodeHuffmanDecoder.cpp	Sat Mar 03 10:31:27 2012 -0600
     1.3 @@ -0,0 +1,89 @@
     1.4 +// ImplodeHuffmanDecoder.cpp
     1.5 +
     1.6 +#include "StdAfx.h"
     1.7 +
     1.8 +#include "ImplodeHuffmanDecoder.h"
     1.9 +
    1.10 +namespace NCompress {
    1.11 +namespace NImplode {
    1.12 +namespace NHuffman {
    1.13 +
    1.14 +CDecoder::CDecoder(UInt32 numSymbols):
    1.15 +  m_NumSymbols(numSymbols)
    1.16 +{
    1.17 +  m_Symbols = new UInt32[m_NumSymbols];
    1.18 +}
    1.19 +
    1.20 +CDecoder::~CDecoder()
    1.21 +{
    1.22 +  delete []m_Symbols;
    1.23 +}
    1.24 +
    1.25 +bool CDecoder::SetCodeLengths(const Byte *codeLengths)
    1.26 +{
    1.27 +  // int lenCounts[kNumBitsInLongestCode + 1], tmpPositions[kNumBitsInLongestCode + 1];
    1.28 +  int lenCounts[kNumBitsInLongestCode + 2], tmpPositions[kNumBitsInLongestCode + 1];
    1.29 +  int i;
    1.30 +  for(i = 0; i <= kNumBitsInLongestCode; i++)
    1.31 +    lenCounts[i] = 0;
    1.32 +  UInt32 symbolIndex;
    1.33 +  for (symbolIndex = 0; symbolIndex < m_NumSymbols; symbolIndex++)
    1.34 +    lenCounts[codeLengths[symbolIndex]]++;
    1.35 +  // lenCounts[0] = 0;
    1.36 +  
    1.37 +  // tmpPositions[0] = m_Positions[0] = m_Limitits[0] = 0;
    1.38 +  m_Limitits[kNumBitsInLongestCode + 1] = 0;
    1.39 +  m_Positions[kNumBitsInLongestCode + 1] = 0;
    1.40 +  lenCounts[kNumBitsInLongestCode + 1] = 0;
    1.41 +
    1.42 +
    1.43 +  UInt32 startPos = 0;
    1.44 +  static const UInt32 kMaxValue = (1 << kNumBitsInLongestCode);
    1.45 +
    1.46 +  for (i = kNumBitsInLongestCode; i > 0; i--)
    1.47 +  {
    1.48 +    startPos += lenCounts[i] << (kNumBitsInLongestCode - i);
    1.49 +    if (startPos > kMaxValue)
    1.50 +      return false;
    1.51 +    m_Limitits[i] = startPos;
    1.52 +    m_Positions[i] = m_Positions[i + 1] + lenCounts[i + 1];
    1.53 +    tmpPositions[i] = m_Positions[i] + lenCounts[i];
    1.54 +
    1.55 +  }
    1.56 +
    1.57 +  // if _ZIP_MODE do not throw exception for trees containing only one node
    1.58 +  // #ifndef _ZIP_MODE
    1.59 +  if (startPos != kMaxValue)
    1.60 +    return false;
    1.61 +  // #endif
    1.62 +
    1.63 +  for (symbolIndex = 0; symbolIndex < m_NumSymbols; symbolIndex++)
    1.64 +    if (codeLengths[symbolIndex] != 0)
    1.65 +      m_Symbols[--tmpPositions[codeLengths[symbolIndex]]] = symbolIndex;
    1.66 +  return true;
    1.67 +}
    1.68 +
    1.69 +UInt32 CDecoder::DecodeSymbol(CInBit *inStream)
    1.70 +{
    1.71 +  UInt32 numBits = 0;
    1.72 +  UInt32 value = inStream->GetValue(kNumBitsInLongestCode);
    1.73 +  int i;
    1.74 +  for(i = kNumBitsInLongestCode; i > 0; i--)
    1.75 +  {
    1.76 +    if (value < m_Limitits[i])
    1.77 +    {
    1.78 +      numBits = i;
    1.79 +      break;
    1.80 +    }
    1.81 +  }
    1.82 +  if (i == 0)
    1.83 +    return 0xFFFFFFFF;
    1.84 +  inStream->MovePos(numBits);
    1.85 +  UInt32 index = m_Positions[numBits] +
    1.86 +      ((value - m_Limitits[numBits + 1]) >> (kNumBitsInLongestCode - numBits));
    1.87 +  if (index >= m_NumSymbols)
    1.88 +    return 0xFFFFFFFF;
    1.89 +  return m_Symbols[index];
    1.90 +}
    1.91 +
    1.92 +}}}