1 // LzmsDecoder.h 2 // The code is based on LZMS description from wimlib code 3 4 #ifndef ZIP7_INC_LZMS_DECODER_H 5 #define ZIP7_INC_LZMS_DECODER_H 6 7 #include "../../../C/CpuArch.h" 8 #include "../../../C/HuffEnc.h" 9 10 #include "HuffmanDecoder.h" 11 12 namespace NCompress { 13 namespace NLzms { 14 15 const unsigned k_NumLitSyms = 256; 16 const unsigned k_NumLenSyms = 54; 17 const unsigned k_NumPosSyms = 799; 18 const unsigned k_NumPowerSyms = 8; 19 20 const unsigned k_NumProbBits = 6; 21 const unsigned k_ProbLimit = 1 << k_NumProbBits; 22 const unsigned k_InitialProb = 48; 23 const UInt32 k_InitialHist = 0x55555555; 24 25 const unsigned k_NumReps = 3; 26 27 const unsigned k_NumMainProbs = 16; 28 const unsigned k_NumMatchProbs = 32; 29 const unsigned k_NumRepProbs = 64; 30 31 const unsigned k_NumHuffmanBits = 15; 32 33 template <UInt32 m_NumSyms, UInt32 m_RebuildFreq, unsigned numTableBits> 34 class CHuffDecoder: public NCompress::NHuffman::CDecoder<k_NumHuffmanBits, m_NumSyms, numTableBits> 35 { 36 public: 37 UInt32 RebuildRem; 38 UInt32 NumSyms; 39 UInt32 Freqs[m_NumSyms]; 40 Generate()41 void Generate() throw() 42 { 43 UInt32 vals[m_NumSyms]; 44 Byte levels[m_NumSyms]; 45 46 // We need to check that our algorithm is OK, when optimal Huffman tree uses more than 15 levels !!! 47 Huffman_Generate(Freqs, vals, levels, NumSyms, k_NumHuffmanBits); 48 49 for (UInt32 i = NumSyms; i < m_NumSyms; i++) 50 levels[i] = 0; 51 52 this->Build(levels, /* NumSyms, */ NHuffman::k_BuildMode_Full); 53 } 54 Rebuild()55 void Rebuild() throw() 56 { 57 Generate(); 58 RebuildRem = m_RebuildFreq; 59 const UInt32 num = NumSyms; 60 for (UInt32 i = 0; i < num; i++) 61 Freqs[i] = (Freqs[i] >> 1) + 1; 62 } 63 64 public: throw()65 void Init(UInt32 numSyms = m_NumSyms) throw() 66 { 67 RebuildRem = m_RebuildFreq; 68 NumSyms = numSyms; 69 for (UInt32 i = 0; i < numSyms; i++) 70 Freqs[i] = 1; 71 // for (; i < m_NumSyms; i++) Freqs[i] = 0; 72 Generate(); 73 } 74 }; 75 76 77 struct CProbEntry 78 { 79 UInt32 Prob; 80 UInt64 Hist; 81 InitCProbEntry82 void Init() 83 { 84 Prob = k_InitialProb; 85 Hist = k_InitialHist; 86 } 87 GetProbCProbEntry88 UInt32 GetProb() const throw() 89 { 90 UInt32 prob = Prob; 91 if (prob == 0) 92 prob = 1; 93 else if (prob == k_ProbLimit) 94 prob = k_ProbLimit - 1; 95 return prob; 96 } 97 UpdateCProbEntry98 void Update(unsigned bit) throw() 99 { 100 Prob += (UInt32)((Int32)(Hist >> (k_ProbLimit - 1)) - (Int32)bit); 101 Hist = (Hist << 1) | bit; 102 } 103 }; 104 105 106 struct CRangeDecoder 107 { 108 UInt32 range; 109 UInt32 code; 110 const Byte *cur; 111 // const Byte *end; 112 InitCRangeDecoder113 void Init(const Byte *data, size_t /* size */) throw() 114 { 115 range = 0xFFFFFFFF; 116 code = (((UInt32)GetUi16(data)) << 16) | GetUi16(data + 2); 117 cur = data + 4; 118 // end = data + size; 119 } 120 NormalizeCRangeDecoder121 void Normalize() 122 { 123 if (range <= 0xFFFF) 124 { 125 range <<= 16; 126 code <<= 16; 127 // if (cur >= end) throw 1; 128 code |= GetUi16(cur); 129 cur += 2; 130 } 131 } 132 DecodeCRangeDecoder133 unsigned Decode(UInt32 *state, UInt32 numStates, struct CProbEntry *probs) 134 { 135 UInt32 st = *state; 136 CProbEntry *entry = &probs[st]; 137 st = (st << 1) & (numStates - 1); 138 139 const UInt32 prob = entry->GetProb(); 140 141 if (range <= 0xFFFF) 142 { 143 range <<= 16; 144 code <<= 16; 145 // if (cur >= end) throw 1; 146 code |= GetUi16(cur); 147 cur += 2; 148 } 149 150 const UInt32 bound = (range >> k_NumProbBits) * prob; 151 152 if (code < bound) 153 { 154 range = bound; 155 *state = st; 156 entry->Update(0); 157 return 0; 158 } 159 else 160 { 161 range -= bound; 162 code -= bound; 163 *state = st | 1; 164 entry->Update(1); 165 return 1; 166 } 167 } 168 }; 169 170 171 class CDecoder 172 { 173 // CRangeDecoder _rc; 174 size_t _pos; 175 176 UInt32 _reps[k_NumReps + 1]; 177 UInt64 _deltaReps[k_NumReps + 1]; 178 179 UInt32 mainState; 180 UInt32 matchState; 181 UInt32 lzRepStates[k_NumReps]; 182 UInt32 deltaRepStates[k_NumReps]; 183 184 struct CProbEntry mainProbs[k_NumMainProbs]; 185 struct CProbEntry matchProbs[k_NumMatchProbs]; 186 187 struct CProbEntry lzRepProbs[k_NumReps][k_NumRepProbs]; 188 struct CProbEntry deltaRepProbs[k_NumReps][k_NumRepProbs]; 189 190 CHuffDecoder<k_NumLitSyms, 1024, 9> m_LitDecoder; 191 CHuffDecoder<k_NumPosSyms, 1024, 9> m_PosDecoder; 192 CHuffDecoder<k_NumLenSyms, 512, 8> m_LenDecoder; 193 CHuffDecoder<k_NumPowerSyms, 512, 6> m_PowerDecoder; 194 CHuffDecoder<k_NumPosSyms, 1024, 9> m_DeltaDecoder; 195 196 Int32 *_x86_history; 197 198 HRESULT CodeReal(const Byte *in, size_t inSize, Byte *out, size_t outSize); 199 public: 200 CDecoder(); 201 ~CDecoder(); 202 203 HRESULT Code(const Byte *in, size_t inSize, Byte *out, size_t outSize); GetUnpackSize()204 size_t GetUnpackSize() const { return _pos; } 205 }; 206 207 }} 208 209 #endif 210