Mercurial > vba-linux

     1 // ImplodeHuffmanDecoder.cpp

     2 

     3 #include "StdAfx.h"

     4 

     5 #include "ImplodeHuffmanDecoder.h"

     6 

     7 namespace NCompress {

     8 namespace NImplode {

     9 namespace NHuffman {

    10 

    11 CDecoder::CDecoder(UInt32 numSymbols):

    12   m_NumSymbols(numSymbols)

    13 {

    14   m_Symbols = new UInt32[m_NumSymbols];

    15 }

    16 

    17 CDecoder::~CDecoder()

    18 {

    19   delete []m_Symbols;

    20 }

    21 

    22 bool CDecoder::SetCodeLengths(const Byte *codeLengths)

    23 {

    24   // int lenCounts[kNumBitsInLongestCode + 1], tmpPositions[kNumBitsInLongestCode + 1];

    25   int lenCounts[kNumBitsInLongestCode + 2], tmpPositions[kNumBitsInLongestCode + 1];

    26   int i;

    27   for(i = 0; i <= kNumBitsInLongestCode; i++)

    28     lenCounts[i] = 0;

    29   UInt32 symbolIndex;

    30   for (symbolIndex = 0; symbolIndex < m_NumSymbols; symbolIndex++)

    31     lenCounts[codeLengths[symbolIndex]]++;

    32   // lenCounts[0] = 0;

    33   

    34   // tmpPositions[0] = m_Positions[0] = m_Limitits[0] = 0;

    35   m_Limitits[kNumBitsInLongestCode + 1] = 0;

    36   m_Positions[kNumBitsInLongestCode + 1] = 0;

    37   lenCounts[kNumBitsInLongestCode + 1] = 0;

    38 

    39 

    40   UInt32 startPos = 0;

    41   static const UInt32 kMaxValue = (1 << kNumBitsInLongestCode);

    42 

    43   for (i = kNumBitsInLongestCode; i > 0; i--)

    44   {

    45     startPos += lenCounts[i] << (kNumBitsInLongestCode - i);

    46     if (startPos > kMaxValue)

    47       return false;

    48     m_Limitits[i] = startPos;

    49     m_Positions[i] = m_Positions[i + 1] + lenCounts[i + 1];

    50     tmpPositions[i] = m_Positions[i] + lenCounts[i];

    51 

    52   }

    53 

    54   // if _ZIP_MODE do not throw exception for trees containing only one node

    55   // #ifndef _ZIP_MODE

    56   if (startPos != kMaxValue)

    57     return false;

    58   // #endif

    59 

    60   for (symbolIndex = 0; symbolIndex < m_NumSymbols; symbolIndex++)

    61     if (codeLengths[symbolIndex] != 0)

    62       m_Symbols[--tmpPositions[codeLengths[symbolIndex]]] = symbolIndex;

    63   return true;

    64 }

    65 

    66 UInt32 CDecoder::DecodeSymbol(CInBit *inStream)

    67 {

    68   UInt32 numBits = 0;

    69   UInt32 value = inStream->GetValue(kNumBitsInLongestCode);

    70   int i;

    71   for(i = kNumBitsInLongestCode; i > 0; i--)

    72   {

    73     if (value < m_Limitits[i])

    74     {

    75       numBits = i;

    76       break;

    77     }

    78   }

    79   if (i == 0)

    80     return 0xFFFFFFFF;

    81   inStream->MovePos(numBits);

    82   UInt32 index = m_Positions[numBits] +

    83       ((value - m_Limitits[numBits + 1]) >> (kNumBitsInLongestCode - numBits));

    84   if (index >= m_NumSymbols)

    85     return 0xFFFFFFFF;

    86   return m_Symbols[index];

    87 }

    88 

    89 }}}
author	Robert McIntyre <rlm@mit.edu>
date	Sat, 03 Mar 2012 10:31:27 -0600
parents
children