Welcome to mirror list, hosted at ThFree Co, Russian Federation.

github.com/kornelski/7z.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/CPP/7zip/Compress/HuffmanDecoder.h
diff options
context:
space:
mode:
Diffstat (limited to 'CPP/7zip/Compress/HuffmanDecoder.h')
-rw-r--r--CPP/7zip/Compress/HuffmanDecoder.h247
1 files changed, 205 insertions, 42 deletions
diff --git a/CPP/7zip/Compress/HuffmanDecoder.h b/CPP/7zip/Compress/HuffmanDecoder.h
index 65e0f93c..04364c14 100644
--- a/CPP/7zip/Compress/HuffmanDecoder.h
+++ b/CPP/7zip/Compress/HuffmanDecoder.h
@@ -8,42 +8,89 @@
namespace NCompress {
namespace NHuffman {
-const unsigned kNumTableBits = 9;
-
-template <unsigned kNumBitsMax, UInt32 m_NumSymbols>
+template <unsigned kNumBitsMax, UInt32 m_NumSymbols, unsigned kNumTableBits = 9>
class CDecoder
{
- UInt32 m_Limits[kNumBitsMax + 1]; // m_Limits[i] = value limit for symbols with length = i
- UInt32 m_Positions[kNumBitsMax + 1]; // m_Positions[i] = index in m_Symbols[] of first symbol with length = i
- UInt32 m_Symbols[m_NumSymbols];
- Byte m_Lengths[1 << kNumTableBits]; // Table of length for short codes
-
+ UInt32 _limits[kNumBitsMax + 2];
+ UInt32 _poses[kNumBitsMax + 1];
+ UInt16 _lens[1 << kNumTableBits];
+ UInt16 _symbols[m_NumSymbols];
public:
- bool SetCodeLengths(const Byte *lens)
+ bool Build(const Byte *lens) throw()
{
UInt32 lenCounts[kNumBitsMax + 1];
- UInt32 tmpPositions[kNumBitsMax + 1];
+ UInt32 tmpPoses[kNumBitsMax + 1];
unsigned i;
- for (i = 1; i <= kNumBitsMax; i++)
+ for (i = 0; i <= kNumBitsMax; i++)
lenCounts[i] = 0;
- UInt32 symbol;
+ UInt32 sym;
+
+ for (sym = 0; sym < m_NumSymbols; sym++)
+ lenCounts[lens[sym]]++;
+
+ lenCounts[0] = 0;
+ _poses[0] = 0;
+ _limits[0] = 0;
+ UInt32 startPos = 0;
+ const UInt32 kMaxValue = (UInt32)1 << kNumBitsMax;
- for (symbol = 0; symbol < m_NumSymbols; symbol++)
+ for (i = 1; i <= kNumBitsMax; i++)
{
- unsigned len = lens[symbol];
- if (len > kNumBitsMax)
+ startPos += lenCounts[i] << (kNumBitsMax - i);
+ if (startPos > kMaxValue)
return false;
- lenCounts[len]++;
- m_Symbols[symbol] = 0xFFFFFFFF;
+ _limits[i] = startPos;
+ _poses[i] = _poses[i - 1] + lenCounts[i - 1];
+ tmpPoses[i] = _poses[i];
+ }
+
+ _limits[kNumBitsMax + 1] = kMaxValue;
+
+ for (sym = 0; sym < m_NumSymbols; sym++)
+ {
+ unsigned len = lens[sym];
+ if (len == 0)
+ continue;
+
+ unsigned offset = tmpPoses[len];
+ _symbols[offset] = (UInt16)sym;
+ tmpPoses[len] = offset + 1;
+
+ if (len <= kNumTableBits)
+ {
+ offset -= _poses[len];
+ UInt32 num = (UInt32)1 << (kNumTableBits - len);
+ UInt16 val = (UInt16)((sym << 4) | len);
+ UInt16 *dest = _lens + (_limits[len - 1] >> (kNumBitsMax - kNumTableBits)) + (offset << (kNumTableBits - len));
+ for (UInt32 k = 0; k < num; k++)
+ dest[k] = val;
+ }
}
+ return true;
+ }
+
+ bool BuildFull(const Byte *lens, UInt32 numSymbols = m_NumSymbols) throw()
+ {
+ UInt32 lenCounts[kNumBitsMax + 1];
+ UInt32 tmpPoses[kNumBitsMax + 1];
+
+ unsigned i;
+ for (i = 0; i <= kNumBitsMax; i++)
+ lenCounts[i] = 0;
+
+ UInt32 sym;
+
+ for (sym = 0; sym < numSymbols; sym++)
+ lenCounts[lens[sym]]++;
+
lenCounts[0] = 0;
- m_Positions[0] = m_Limits[0] = 0;
+ _poses[0] = 0;
+ _limits[0] = 0;
UInt32 startPos = 0;
- UInt32 index = 0;
const UInt32 kMaxValue = (UInt32)1 << kNumBitsMax;
for (i = 1; i <= kNumBitsMax; i++)
@@ -51,44 +98,160 @@ public:
startPos += lenCounts[i] << (kNumBitsMax - i);
if (startPos > kMaxValue)
return false;
- m_Limits[i] = (i == kNumBitsMax) ? kMaxValue : startPos;
- m_Positions[i] = m_Positions[i - 1] + lenCounts[i - 1];
- tmpPositions[i] = m_Positions[i];
- if (i <= kNumTableBits)
+ _limits[i] = startPos;
+ _poses[i] = _poses[i - 1] + lenCounts[i - 1];
+ tmpPoses[i] = _poses[i];
+ }
+
+ _limits[kNumBitsMax + 1] = kMaxValue;
+
+ for (sym = 0; sym < numSymbols; sym++)
+ {
+ unsigned len = lens[sym];
+ if (len == 0)
+ continue;
+
+ unsigned offset = tmpPoses[len];
+ _symbols[offset] = (UInt16)sym;
+ tmpPoses[len] = offset + 1;
+
+ if (len <= kNumTableBits)
{
- UInt32 limit = (m_Limits[i] >> (kNumBitsMax - kNumTableBits));
- for (; index < limit; index++)
- m_Lengths[index] = (Byte)i;
+ offset -= _poses[len];
+ UInt32 num = (UInt32)1 << (kNumTableBits - len);
+ UInt16 val = (UInt16)((sym << 4) | len);
+ UInt16 *dest = _lens + (_limits[len - 1] >> (kNumBitsMax - kNumTableBits)) + (offset << (kNumTableBits - len));
+ for (UInt32 k = 0; k < num; k++)
+ dest[k] = val;
}
}
- for (symbol = 0; symbol < m_NumSymbols; symbol++)
+ return startPos == kMaxValue;
+ }
+
+ template <class TBitDecoder>
+ UInt32 Decode(TBitDecoder *bitStream) const throw()
+ {
+ UInt32 val = bitStream->GetValue(kNumBitsMax);
+
+ if (val < _limits[kNumTableBits])
{
- unsigned len = lens[symbol];
- if (len != 0)
- m_Symbols[tmpPositions[len]++] = symbol;
+ UInt32 pair = _lens[val >> (kNumBitsMax - kNumTableBits)];
+ bitStream->MovePos((unsigned)(pair & 0xF));
+ return pair >> 4;
}
+
+ unsigned numBits;
+ for (numBits = kNumTableBits + 1; val >= _limits[numBits]; numBits++);
- return true;
+ if (numBits > kNumBitsMax)
+ return 0xFFFFFFFF;
+
+ bitStream->MovePos(numBits);
+ UInt32 index = _poses[numBits] + ((val - _limits[numBits - 1]) >> (kNumBitsMax - numBits));
+ return _symbols[index];
}
template <class TBitDecoder>
- UInt32 DecodeSymbol(TBitDecoder *bitStream)
+ UInt32 DecodeFull(TBitDecoder *bitStream) const throw()
{
- unsigned numBits;
UInt32 val = bitStream->GetValue(kNumBitsMax);
- if (val < m_Limits[kNumTableBits])
- numBits = m_Lengths[val >> (kNumBitsMax - kNumTableBits)];
- else
- for (numBits = kNumTableBits + 1; val >= m_Limits[numBits]; numBits++);
+ if (val < _limits[kNumTableBits])
+ {
+ UInt32 pair = _lens[val >> (kNumBitsMax - kNumTableBits)];
+ bitStream->MovePos((unsigned)(pair & 0xF));
+ return pair >> 4;
+ }
+
+ unsigned numBits;
+ for (numBits = kNumTableBits + 1; val >= _limits[numBits]; numBits++);
bitStream->MovePos(numBits);
- UInt32 index = m_Positions[numBits] + ((val - m_Limits[numBits - 1]) >> (kNumBitsMax - numBits));
- if (index >= m_NumSymbols)
- // throw CDecoderException(); // test it
- return 0xFFFFFFFF;
- return m_Symbols[index];
+ UInt32 index = _poses[numBits] + ((val - _limits[numBits - 1]) >> (kNumBitsMax - numBits));
+ return _symbols[index];
+ }
+};
+
+
+
+template <UInt32 m_NumSymbols>
+class CDecoder7b
+{
+ Byte _lens[1 << 7];
+public:
+
+ bool Build(const Byte *lens) throw()
+ {
+ const unsigned kNumBitsMax = 7;
+
+ UInt32 lenCounts[kNumBitsMax + 1];
+ UInt32 tmpPoses[kNumBitsMax + 1];
+ UInt32 _poses[kNumBitsMax + 1];
+ UInt32 _limits[kNumBitsMax + 1];
+
+ unsigned i;
+ for (i = 0; i <= kNumBitsMax; i++)
+ lenCounts[i] = 0;
+
+ UInt32 sym;
+
+ for (sym = 0; sym < m_NumSymbols; sym++)
+ lenCounts[lens[sym]]++;
+
+ lenCounts[0] = 0;
+ _poses[0] = 0;
+ _limits[0] = 0;
+ UInt32 startPos = 0;
+ const UInt32 kMaxValue = (UInt32)1 << kNumBitsMax;
+
+ for (i = 1; i <= kNumBitsMax; i++)
+ {
+ startPos += lenCounts[i] << (kNumBitsMax - i);
+ if (startPos > kMaxValue)
+ return false;
+ _limits[i] = startPos;
+ _poses[i] = _poses[i - 1] + lenCounts[i - 1];
+ tmpPoses[i] = _poses[i];
+ }
+
+ for (sym = 0; sym < m_NumSymbols; sym++)
+ {
+ unsigned len = lens[sym];
+ if (len == 0)
+ continue;
+
+ unsigned offset = tmpPoses[len];
+ tmpPoses[len] = offset + 1;
+
+ {
+ offset -= _poses[len];
+ UInt32 num = (UInt32)1 << (kNumBitsMax - len);
+ Byte val = (Byte)((sym << 3) | len);
+ Byte *dest = _lens + (_limits[len - 1]) + (offset << (kNumBitsMax - len));
+ for (UInt32 k = 0; k < num; k++)
+ dest[k] = val;
+ }
+ }
+
+ {
+ UInt32 limit = _limits[kNumBitsMax];
+ UInt32 num = ((UInt32)1 << kNumBitsMax) - limit;
+ Byte *dest = _lens + limit;
+ for (UInt32 k = 0; k < num; k++)
+ dest[k] = (Byte)(0x1F << 3);
+ }
+
+ return true;
+ }
+
+ template <class TBitDecoder>
+ UInt32 Decode(TBitDecoder *bitStream) const throw()
+ {
+ UInt32 val = bitStream->GetValue(7);
+ UInt32 pair = _lens[val];
+ bitStream->MovePos((unsigned)(pair & 0x7));
+ return pair >> 3;
}
};
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-28 13:28:56 +0300