CPP/7zip/Compress/ImplodeHuffmanDecoder.cpp

   1 // ImplodeHuffmanDecoder.cpp\r
   2 \r
   3 #include "StdAfx.h"\r
   4 \r
   5 #include "ImplodeHuffmanDecoder.h"\r
   6 \r
   7 namespace NCompress {\r
   8 namespace NImplode {\r
   9 namespace NHuffman {\r
  10 \r
  11 CDecoder::CDecoder(UInt32 numSymbols):\r
  12   m_NumSymbols(numSymbols)\r
  13 {\r
  14   m_Symbols = new UInt32[m_NumSymbols];\r
  15 }\r
  16 \r
  17 CDecoder::~CDecoder()\r
  18 {\r
  19   delete []m_Symbols;\r
  20 }\r
  21 \r
  22 bool CDecoder::SetCodeLengths(const Byte *codeLengths)\r
  23 {\r
  24   // int lenCounts[kNumBitsInLongestCode + 1], tmpPositions[kNumBitsInLongestCode + 1];\r
  25   int lenCounts[kNumBitsInLongestCode + 2], tmpPositions[kNumBitsInLongestCode + 1];\r
  26   int i;\r
  27   for(i = 0; i <= kNumBitsInLongestCode; i++)\r
  28     lenCounts[i] = 0;\r
  29   UInt32 symbolIndex;\r
  30   for (symbolIndex = 0; symbolIndex < m_NumSymbols; symbolIndex++)\r
  31     lenCounts[codeLengths[symbolIndex]]++;\r
  32   // lenCounts[0] = 0;\r
  33   \r
  34   // tmpPositions[0] = m_Positions[0] = m_Limitits[0] = 0;\r
  35   m_Limitits[kNumBitsInLongestCode + 1] = 0;\r
  36   m_Positions[kNumBitsInLongestCode + 1] = 0;\r
  37   lenCounts[kNumBitsInLongestCode + 1] =  0;\r
  38 \r
  39 \r
  40   UInt32 startPos = 0;\r
  41   static const UInt32 kMaxValue = (1 << kNumBitsInLongestCode);\r
  42 \r
  43   for (i = kNumBitsInLongestCode; i > 0; i--)\r
  44   {\r
  45     startPos += lenCounts[i] << (kNumBitsInLongestCode - i);\r
  46     if (startPos > kMaxValue)\r
  47       return false;\r
  48     m_Limitits[i] = startPos;\r
  49     m_Positions[i] = m_Positions[i + 1] + lenCounts[i + 1];\r
  50     tmpPositions[i] = m_Positions[i] + lenCounts[i];\r
  51 \r
  52   }\r
  53 \r
  54   // if _ZIP_MODE do not throw exception for trees containing only one node\r
  55   // #ifndef _ZIP_MODE\r
  56   if (startPos != kMaxValue)\r
  57     return false;\r
  58   // #endif\r
  59 \r
  60   for (symbolIndex = 0; symbolIndex < m_NumSymbols; symbolIndex++)\r
  61     if (codeLengths[symbolIndex] != 0)\r
  62       m_Symbols[--tmpPositions[codeLengths[symbolIndex]]] = symbolIndex;\r
  63   return true;\r
  64 }\r
  65 \r
  66 UInt32 CDecoder::DecodeSymbol(CInBit *inStream)\r
  67 {\r
  68   UInt32 numBits = 0;\r
  69   UInt32 value = inStream->GetValue(kNumBitsInLongestCode);\r
  70   int i;\r
  71   for(i = kNumBitsInLongestCode; i > 0; i--)\r
  72   {\r
  73     if (value < m_Limitits[i])\r
  74     {\r
  75       numBits = i;\r
  76       break;\r
  77     }\r
  78   }\r
  79   if (i == 0)\r
  80     return 0xFFFFFFFF;\r
  81   inStream->MovePos(numBits);\r
  82   UInt32 index = m_Positions[numBits] +\r
  83       ((value - m_Limitits[numBits + 1]) >> (kNumBitsInLongestCode - numBits));\r
  84   if (index >= m_NumSymbols)\r
  85     return 0xFFFFFFFF;\r
  86   return m_Symbols[index];\r
  87 }\r
  88 \r
  89 }}}\r