CPP/7zip/Compress/HuffmanDecoder.h

   1 // Compress/HuffmanDecoder.h\r
   2 \r
   3 #ifndef __COMPRESS_HUFFMAN_DECODER_H\r
   4 #define __COMPRESS_HUFFMAN_DECODER_H\r
   5 \r
   6 #include "../../Common/Types.h"\r
   7 \r
   8 namespace NCompress {\r
   9 namespace NHuffman {\r
  10 \r
  11 const int kNumTableBits = 9;\r
  12 \r
  13 template <int kNumBitsMax, UInt32 m_NumSymbols>\r
  14 class CDecoder\r
  15 {\r
  16   UInt32 m_Limits[kNumBitsMax + 1];     // m_Limits[i] = value limit for symbols with length = i\r
  17   UInt32 m_Positions[kNumBitsMax + 1];  // m_Positions[i] = index in m_Symbols[] of first symbol with length = i\r
  18   UInt32 m_Symbols[m_NumSymbols];\r
  19   Byte m_Lengths[1 << kNumTableBits];   // Table oh length for short codes.\r
  20 \r
  21 public:\r
  22   \r
  23   bool SetCodeLengths(const Byte *codeLengths)\r
  24   {\r
  25     int lenCounts[kNumBitsMax + 1];\r
  26     UInt32 tmpPositions[kNumBitsMax + 1];\r
  27     int i;\r
  28     for(i = 1; i <= kNumBitsMax; i++)\r
  29       lenCounts[i] = 0;\r
  30     UInt32 symbol;\r
  31     for (symbol = 0; symbol < m_NumSymbols; symbol++)\r
  32     {\r
  33       int len = codeLengths[symbol];\r
  34       if (len > kNumBitsMax)\r
  35         return false;\r
  36       lenCounts[len]++;\r
  37       m_Symbols[symbol] = 0xFFFFFFFF;\r
  38     }\r
  39     lenCounts[0] = 0;\r
  40     m_Positions[0] = m_Limits[0] = 0;\r
  41     UInt32 startPos = 0;\r
  42     UInt32 index = 0;\r
  43     const UInt32 kMaxValue = (1 << kNumBitsMax);\r
  44     for (i = 1; i <= kNumBitsMax; i++)\r
  45     {\r
  46       startPos += lenCounts[i] << (kNumBitsMax - i);\r
  47       if (startPos > kMaxValue)\r
  48         return false;\r
  49       m_Limits[i] = (i == kNumBitsMax) ? kMaxValue : startPos;\r
  50       m_Positions[i] = m_Positions[i - 1] + lenCounts[i - 1];\r
  51       tmpPositions[i] = m_Positions[i];\r
  52       if(i <= kNumTableBits)\r
  53       {\r
  54         UInt32 limit = (m_Limits[i] >> (kNumBitsMax - kNumTableBits));\r
  55         for (; index < limit; index++)\r
  56           m_Lengths[index] = (Byte)i;\r
  57       }\r
  58     }\r
  59     for (symbol = 0; symbol < m_NumSymbols; symbol++)\r
  60     {\r
  61       int len = codeLengths[symbol];\r
  62       if (len != 0)\r
  63         m_Symbols[tmpPositions[len]++] = symbol;\r
  64     }\r
  65     return true;\r
  66   }\r
  67 \r
  68   template <class TBitDecoder>\r
  69   UInt32 DecodeSymbol(TBitDecoder *bitStream)\r
  70   {\r
  71     int numBits;\r
  72     UInt32 value = bitStream->GetValue(kNumBitsMax);\r
  73     if (value < m_Limits[kNumTableBits])\r
  74       numBits = m_Lengths[value >> (kNumBitsMax - kNumTableBits)];\r
  75     else\r
  76       for (numBits = kNumTableBits + 1; value >= m_Limits[numBits]; numBits++);\r
  77     bitStream->MovePos(numBits);\r
  78     UInt32 index = m_Positions[numBits] +\r
  79       ((value - m_Limits[numBits - 1]) >> (kNumBitsMax - numBits));\r
  80     if (index >= m_NumSymbols)\r
  81       // throw CDecoderException(); // test it\r
  82       return 0xFFFFFFFF;\r
  83     return m_Symbols[index];\r
  84   }\r
  85 };\r
  86 \r
  87 }}\r
  88 \r
  89 #endif\r