Mercurial > vba-linux

     1 // Compress/HuffmanDecoder.h

     2 

     3 #ifndef __COMPRESS_HUFFMAN_DECODER_H

     4 #define __COMPRESS_HUFFMAN_DECODER_H

     5 

     6 #include "../../Common/Types.h"

     7 

     8 namespace NCompress {

     9 namespace NHuffman {

    10 

    11 const int kNumTableBits = 9;

    12 

    13 template <int kNumBitsMax, UInt32 m_NumSymbols>

    14 class CDecoder

    15 {

    16   UInt32 m_Limits[kNumBitsMax + 1];     // m_Limits[i] = value limit for symbols with length = i

    17   UInt32 m_Positions[kNumBitsMax + 1];  // m_Positions[i] = index in m_Symbols[] of first symbol with length = i

    18   UInt32 m_Symbols[m_NumSymbols];

    19   Byte m_Lengths[1 << kNumTableBits];   // Table oh length for short codes.

    20 

    21 public:

    22   

    23   bool SetCodeLengths(const Byte *codeLengths)

    24   {

    25     int lenCounts[kNumBitsMax + 1];

    26     UInt32 tmpPositions[kNumBitsMax + 1];

    27     int i;

    28     for(i = 1; i <= kNumBitsMax; i++)

    29       lenCounts[i] = 0;

    30     UInt32 symbol;

    31     for (symbol = 0; symbol < m_NumSymbols; symbol++)

    32     {

    33       int len = codeLengths[symbol];

    34       if (len > kNumBitsMax)

    35         return false;

    36       lenCounts[len]++;

    37       m_Symbols[symbol] = 0xFFFFFFFF;

    38     }

    39     lenCounts[0] = 0;

    40     m_Positions[0] = m_Limits[0] = 0;

    41     UInt32 startPos = 0;

    42     UInt32 index = 0;

    43     const UInt32 kMaxValue = (1 << kNumBitsMax);

    44     for (i = 1; i <= kNumBitsMax; i++)

    45     {

    46       startPos += lenCounts[i] << (kNumBitsMax - i);

    47       if (startPos > kMaxValue)

    48         return false;

    49       m_Limits[i] = (i == kNumBitsMax) ? kMaxValue : startPos;

    50       m_Positions[i] = m_Positions[i - 1] + lenCounts[i - 1];

    51       tmpPositions[i] = m_Positions[i];

    52       if(i <= kNumTableBits)

    53       {

    54         UInt32 limit = (m_Limits[i] >> (kNumBitsMax - kNumTableBits));

    55         for (; index < limit; index++)

    56           m_Lengths[index] = (Byte)i;

    57       }

    58     }

    59     for (symbol = 0; symbol < m_NumSymbols; symbol++)

    60     {

    61       int len = codeLengths[symbol];

    62       if (len != 0)

    63         m_Symbols[tmpPositions[len]++] = symbol;

    64     }

    65     return true;

    66   }

    67 

    68   template <class TBitDecoder>

    69   UInt32 DecodeSymbol(TBitDecoder *bitStream)

    70   {

    71     int numBits;

    72     UInt32 value = bitStream->GetValue(kNumBitsMax);

    73     if (value < m_Limits[kNumTableBits])

    74       numBits = m_Lengths[value >> (kNumBitsMax - kNumTableBits)];

    75     else

    76       for (numBits = kNumTableBits + 1; value >= m_Limits[numBits]; numBits++);

    77     bitStream->MovePos(numBits);

    78     UInt32 index = m_Positions[numBits] +

    79       ((value - m_Limits[numBits - 1]) >> (kNumBitsMax - numBits));

    80     if (index >= m_NumSymbols)

    81       // throw CDecoderException(); // test it

    82       return 0xFFFFFFFF;

    83     return m_Symbols[index];

    84   }

    85 };

    86 

    87 }}

    88 

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