1 // DeflateEncoder.cpp
2
3 #include "StdAfx.h"
4
5 #include "../../../C/Alloc.h"
6 #include "../../../C/HuffEnc.h"
7
8 #include "../../Common/ComTry.h"
9
10 #include "../Common/CWrappers.h"
11
12 #include "DeflateEncoder.h"
13
14 #undef NO_INLINE
15
16 #ifdef _MSC_VER
17 #define NO_INLINE Z7_NO_INLINE
18 #else
19 #define NO_INLINE
20 #endif
21
22 namespace NCompress {
23 namespace NDeflate {
24 namespace NEncoder {
25
26 static const unsigned kNumDivPassesMax = 10; // [0, 16); ratio/speed/ram tradeoff; use big value for better compression ratio.
27 static const UInt32 kNumTables = (1 << kNumDivPassesMax);
28
29 static const UInt32 kFixedHuffmanCodeBlockSizeMax = (1 << 8); // [0, (1 << 32)); ratio/speed tradeoff; use big value for better compression ratio.
30 static const UInt32 kDivideCodeBlockSizeMin = (1 << 7); // [1, (1 << 32)); ratio/speed tradeoff; use small value for better compression ratio.
31 static const UInt32 kDivideBlockSizeMin = (1 << 6); // [1, (1 << 32)); ratio/speed tradeoff; use small value for better compression ratio.
32
33 static const UInt32 kMaxUncompressedBlockSize = ((1 << 16) - 1) * 1; // [1, (1 << 32))
34 static const UInt32 kMatchArraySize = kMaxUncompressedBlockSize * 10; // [kMatchMaxLen * 2, (1 << 32))
35 static const UInt32 kMatchArrayLimit = kMatchArraySize - kMatchMaxLen * 4 * sizeof(UInt16);
36 static const UInt32 kBlockUncompressedSizeThreshold = kMaxUncompressedBlockSize -
37 kMatchMaxLen - kNumOpts;
38
39 // static const unsigned kMaxCodeBitLength = 11;
40 static const unsigned kMaxLevelBitLength = 7;
41
42 static const Byte kNoLiteralStatPrice = 11;
43 static const Byte kNoLenStatPrice = 11;
44 static const Byte kNoPosStatPrice = 6;
45
46 MY_ALIGN(64)
47 static Byte g_LenSlots[kNumLenSymbolsMax];
48
49 #define kNumLogBits 9 // do not change it
50 MY_ALIGN(64)
51 static Byte g_FastPos[1 << kNumLogBits];
52
53 class CFastPosInit
54 {
55 public:
CFastPosInit()56 CFastPosInit()
57 {
58 unsigned i;
59 for (i = 0; i < kNumLenSlots; i++)
60 {
61 unsigned c = kLenStart32[i];
62 const unsigned j = 1u << kLenDirectBits32[i];
63 for (unsigned k = 0; k < j; k++, c++)
64 g_LenSlots[c] = (Byte)i;
65 }
66
67 const unsigned kFastSlots = kNumLogBits * 2;
68 unsigned c = 0;
69 for (Byte slotFast = 0; slotFast < kFastSlots; slotFast++)
70 {
71 const unsigned k = 1u << kDistDirectBits[slotFast];
72 for (unsigned j = 0; j < k; j++, c++)
73 g_FastPos[c] = slotFast;
74 }
75 }
76 };
77
78 static CFastPosInit g_FastPosInit;
79
GetPosSlot(UInt32 pos)80 inline UInt32 GetPosSlot(UInt32 pos)
81 {
82 /*
83 if (pos < 0x200)
84 return g_FastPos[pos];
85 return g_FastPos[pos >> 8] + 16;
86 */
87 // const unsigned zz = (pos < ((UInt32)1 << (kNumLogBits))) ? 0 : 8;
88 /*
89 const unsigned zz = (kNumLogBits - 1) &
90 ((UInt32)0 - (((((UInt32)1 << kNumLogBits) - 1) - pos) >> 31));
91 */
92 const unsigned zz = (kNumLogBits - 1) &
93 (((((UInt32)1 << kNumLogBits) - 1) - pos) >> (31 - 3));
94 return g_FastPos[pos >> zz] + (zz * 2);
95 }
96
97
Normalize()98 void CEncProps::Normalize()
99 {
100 int level = Level;
101 if (level < 0) level = 5;
102 Level = level;
103 if (algo < 0) algo = (level < 5 ? 0 : 1);
104 if (fb < 0) fb = (level < 7 ? 32 : (level < 9 ? 64 : 128));
105 if (btMode < 0) btMode = (algo == 0 ? 0 : 1);
106 if (mc == 0) mc = (16 + ((unsigned)fb >> 1));
107 if (numPasses == (UInt32)(Int32)-1) numPasses = (level < 7 ? 1 : (level < 9 ? 3 : 10));
108 }
109
SetProps(const CEncProps * props2)110 void CCoder::SetProps(const CEncProps *props2)
111 {
112 CEncProps props = *props2;
113 props.Normalize();
114
115 m_MatchFinderCycles = props.mc;
116 {
117 unsigned fb = (unsigned)props.fb;
118 if (fb < kMatchMinLen)
119 fb = kMatchMinLen;
120 if (fb > m_MatchMaxLen)
121 fb = m_MatchMaxLen;
122 m_NumFastBytes = fb;
123 }
124 _fastMode = (props.algo == 0);
125 _btMode = (props.btMode != 0);
126
127 m_NumDivPasses = props.numPasses;
128 if (m_NumDivPasses == 0)
129 m_NumDivPasses = 1;
130 if (m_NumDivPasses == 1)
131 m_NumPasses = 1;
132 else if (m_NumDivPasses <= kNumDivPassesMax)
133 m_NumPasses = 2;
134 else
135 {
136 m_NumPasses = 2 + (m_NumDivPasses - kNumDivPassesMax);
137 m_NumDivPasses = kNumDivPassesMax;
138 }
139 }
140
CCoder(bool deflate64Mode)141 CCoder::CCoder(bool deflate64Mode):
142 m_Values(NULL),
143 m_OnePosMatchesMemory(NULL),
144 m_DistanceMemory(NULL),
145 m_Created(false),
146 m_Deflate64Mode(deflate64Mode),
147 m_Tables(NULL)
148 {
149 m_MatchMaxLen = deflate64Mode ? kMatchMaxLen64 : kMatchMaxLen32;
150 m_NumLenCombinations = deflate64Mode ? kNumLenSymbols64 : kNumLenSymbols32;
151 m_LenStart = deflate64Mode ? kLenStart64 : kLenStart32;
152 m_LenDirectBits = deflate64Mode ? kLenDirectBits64 : kLenDirectBits32;
153 {
154 CEncProps props;
155 SetProps(&props);
156 }
157 MatchFinder_Construct(&_lzInWindow);
158 }
159
Create()160 HRESULT CCoder::Create()
161 {
162 // COM_TRY_BEGIN
163 if (!m_Values)
164 {
165 m_Values = (CCodeValue *)MyAlloc((kMaxUncompressedBlockSize) * sizeof(CCodeValue));
166 if (!m_Values)
167 return E_OUTOFMEMORY;
168 }
169 if (!m_Tables)
170 {
171 m_Tables = (CTables *)MyAlloc((kNumTables) * sizeof(CTables));
172 if (!m_Tables)
173 return E_OUTOFMEMORY;
174 }
175
176 if (m_IsMultiPass)
177 {
178 if (!m_OnePosMatchesMemory)
179 {
180 m_OnePosMatchesMemory = (UInt16 *)::MidAlloc(kMatchArraySize * sizeof(UInt16));
181 if (!m_OnePosMatchesMemory)
182 return E_OUTOFMEMORY;
183 }
184 }
185 else
186 {
187 if (!m_DistanceMemory)
188 {
189 m_DistanceMemory = (UInt16 *)MyAlloc((kMatchMaxLen + 2) * 2 * sizeof(UInt16));
190 if (!m_DistanceMemory)
191 return E_OUTOFMEMORY;
192 m_MatchDistances = m_DistanceMemory;
193 }
194 }
195
196 if (!m_Created)
197 {
198 _lzInWindow.btMode = (Byte)(_btMode ? 1 : 0);
199 _lzInWindow.numHashBytes = 3;
200 _lzInWindow.numHashBytes_Min = 3;
201 if (!MatchFinder_Create(&_lzInWindow,
202 m_Deflate64Mode ? kHistorySize64 : kHistorySize32,
203 kNumOpts + kMaxUncompressedBlockSize,
204 m_NumFastBytes, m_MatchMaxLen - m_NumFastBytes, &g_AlignedAlloc))
205 return E_OUTOFMEMORY;
206 if (!m_OutStream.Create(1 << 20))
207 return E_OUTOFMEMORY;
208 }
209 if (m_MatchFinderCycles != 0)
210 _lzInWindow.cutValue = m_MatchFinderCycles;
211 m_Created = true;
212 return S_OK;
213 // COM_TRY_END
214 }
215
BaseSetEncoderProperties2(const PROPID * propIDs,const PROPVARIANT * coderProps,UInt32 numProps)216 HRESULT CCoder::BaseSetEncoderProperties2(const PROPID *propIDs, const PROPVARIANT *coderProps, UInt32 numProps)
217 {
218 CEncProps props;
219 for (UInt32 i = 0; i < numProps; i++)
220 {
221 const PROPVARIANT &prop = coderProps[i];
222 PROPID propID = propIDs[i];
223 if (propID >= NCoderPropID::kReduceSize)
224 continue;
225 if (prop.vt != VT_UI4)
226 return E_INVALIDARG;
227 UInt32 v = (UInt32)prop.ulVal;
228 switch (propID)
229 {
230 case NCoderPropID::kNumPasses: props.numPasses = v; break;
231 case NCoderPropID::kNumFastBytes: props.fb = (int)v; break;
232 case NCoderPropID::kMatchFinderCycles: props.mc = v; break;
233 case NCoderPropID::kAlgorithm: props.algo = (int)v; break;
234 case NCoderPropID::kLevel: props.Level = (int)v; break;
235 case NCoderPropID::kNumThreads: break;
236 default: return E_INVALIDARG;
237 }
238 }
239 SetProps(&props);
240 return S_OK;
241 }
242
Free()243 void CCoder::Free()
244 {
245 ::MidFree(m_OnePosMatchesMemory); m_OnePosMatchesMemory = NULL;
246 ::MyFree(m_DistanceMemory); m_DistanceMemory = NULL;
247 ::MyFree(m_Values); m_Values = NULL;
248 ::MyFree(m_Tables); m_Tables = NULL;
249 }
250
~CCoder()251 CCoder::~CCoder()
252 {
253 Free();
254 MatchFinder_Free(&_lzInWindow, &g_AlignedAlloc);
255 }
256
GetMatches()257 NO_INLINE void CCoder::GetMatches()
258 {
259 if (m_IsMultiPass)
260 {
261 m_MatchDistances = m_OnePosMatchesMemory + m_Pos;
262 if (m_SecondPass)
263 {
264 m_Pos += *m_MatchDistances + 1;
265 return;
266 }
267 }
268
269 UInt32 distanceTmp[kMatchMaxLen * 2 + 3];
270
271 const UInt32 numPairs = (UInt32)((_btMode ?
272 Bt3Zip_MatchFinder_GetMatches(&_lzInWindow, distanceTmp):
273 Hc3Zip_MatchFinder_GetMatches(&_lzInWindow, distanceTmp)) - distanceTmp);
274
275 *m_MatchDistances = (UInt16)numPairs;
276
277 if (numPairs != 0)
278 {
279 UInt32 i;
280 for (i = 0; i < numPairs; i += 2)
281 {
282 m_MatchDistances[(size_t)i + 1] = (UInt16)distanceTmp[i];
283 m_MatchDistances[(size_t)i + 2] = (UInt16)distanceTmp[(size_t)i + 1];
284 }
285 UInt32 len = distanceTmp[(size_t)numPairs - 2];
286 if (len == m_NumFastBytes && m_NumFastBytes != m_MatchMaxLen)
287 {
288 UInt32 numAvail = Inline_MatchFinder_GetNumAvailableBytes(&_lzInWindow) + 1;
289 const Byte *pby = Inline_MatchFinder_GetPointerToCurrentPos(&_lzInWindow) - 1;
290 const Byte *pby2 = pby - (distanceTmp[(size_t)numPairs - 1] + 1);
291 if (numAvail > m_MatchMaxLen)
292 numAvail = m_MatchMaxLen;
293 for (; len < numAvail && pby[len] == pby2[len]; len++);
294 m_MatchDistances[(size_t)i - 1] = (UInt16)len;
295 }
296 }
297 if (m_IsMultiPass)
298 m_Pos += numPairs + 1;
299 if (!m_SecondPass)
300 m_AdditionalOffset++;
301 }
302
MovePos(UInt32 num)303 void CCoder::MovePos(UInt32 num)
304 {
305 if (!m_SecondPass && num > 0)
306 {
307 if (_btMode)
308 Bt3Zip_MatchFinder_Skip(&_lzInWindow, num);
309 else
310 Hc3Zip_MatchFinder_Skip(&_lzInWindow, num);
311 m_AdditionalOffset += num;
312 }
313 }
314
315 static const UInt32 kIfinityPrice = 0xFFFFFFF;
316
Backward(UInt32 & backRes,UInt32 cur)317 NO_INLINE UInt32 CCoder::Backward(UInt32 &backRes, UInt32 cur)
318 {
319 m_OptimumEndIndex = cur;
320 UInt32 posMem = m_Optimum[cur].PosPrev;
321 UInt16 backMem = m_Optimum[cur].BackPrev;
322 do
323 {
324 UInt32 posPrev = posMem;
325 UInt16 backCur = backMem;
326 backMem = m_Optimum[posPrev].BackPrev;
327 posMem = m_Optimum[posPrev].PosPrev;
328 m_Optimum[posPrev].BackPrev = backCur;
329 m_Optimum[posPrev].PosPrev = (UInt16)cur;
330 cur = posPrev;
331 }
332 while (cur > 0);
333 backRes = m_Optimum[0].BackPrev;
334 m_OptimumCurrentIndex = m_Optimum[0].PosPrev;
335 return m_OptimumCurrentIndex;
336 }
337
GetOptimal(UInt32 & backRes)338 NO_INLINE UInt32 CCoder::GetOptimal(UInt32 &backRes)
339 {
340 if (m_OptimumEndIndex != m_OptimumCurrentIndex)
341 {
342 UInt32 len = m_Optimum[m_OptimumCurrentIndex].PosPrev - m_OptimumCurrentIndex;
343 backRes = m_Optimum[m_OptimumCurrentIndex].BackPrev;
344 m_OptimumCurrentIndex = m_Optimum[m_OptimumCurrentIndex].PosPrev;
345 return len;
346 }
347 m_OptimumCurrentIndex = m_OptimumEndIndex = 0;
348
349 GetMatches();
350
351 UInt32 lenEnd;
352 {
353 const UInt32 numDistancePairs = m_MatchDistances[0];
354 if (numDistancePairs == 0)
355 return 1;
356 const UInt16 *matchDistances = m_MatchDistances + 1;
357 lenEnd = matchDistances[(size_t)numDistancePairs - 2];
358
359 if (lenEnd > m_NumFastBytes)
360 {
361 backRes = matchDistances[(size_t)numDistancePairs - 1];
362 MovePos(lenEnd - 1);
363 return lenEnd;
364 }
365
366 m_Optimum[1].Price = m_LiteralPrices[*(Inline_MatchFinder_GetPointerToCurrentPos(&_lzInWindow) - m_AdditionalOffset)];
367 m_Optimum[1].PosPrev = 0;
368
369 m_Optimum[2].Price = kIfinityPrice;
370 m_Optimum[2].PosPrev = 1;
371
372 UInt32 offs = 0;
373
374 for (UInt32 i = kMatchMinLen; i <= lenEnd; i++)
375 {
376 UInt32 distance = matchDistances[(size_t)offs + 1];
377 m_Optimum[i].PosPrev = 0;
378 m_Optimum[i].BackPrev = (UInt16)distance;
379 m_Optimum[i].Price = m_LenPrices[(size_t)i - kMatchMinLen] + m_PosPrices[GetPosSlot(distance)];
380 if (i == matchDistances[offs])
381 offs += 2;
382 }
383 }
384
385 UInt32 cur = 0;
386
387 for (;;)
388 {
389 ++cur;
390 if (cur == lenEnd || cur == kNumOptsBase || m_Pos >= kMatchArrayLimit)
391 return Backward(backRes, cur);
392 GetMatches();
393 const UInt16 *matchDistances = m_MatchDistances + 1;
394 const UInt32 numDistancePairs = m_MatchDistances[0];
395 UInt32 newLen = 0;
396 if (numDistancePairs != 0)
397 {
398 newLen = matchDistances[(size_t)numDistancePairs - 2];
399 if (newLen > m_NumFastBytes)
400 {
401 UInt32 len = Backward(backRes, cur);
402 m_Optimum[cur].BackPrev = matchDistances[(size_t)numDistancePairs - 1];
403 m_OptimumEndIndex = cur + newLen;
404 m_Optimum[cur].PosPrev = (UInt16)m_OptimumEndIndex;
405 MovePos(newLen - 1);
406 return len;
407 }
408 }
409 UInt32 curPrice = m_Optimum[cur].Price;
410 {
411 const UInt32 curAnd1Price = curPrice + m_LiteralPrices[*(Inline_MatchFinder_GetPointerToCurrentPos(&_lzInWindow) + cur - m_AdditionalOffset)];
412 COptimal &optimum = m_Optimum[(size_t)cur + 1];
413 if (curAnd1Price < optimum.Price)
414 {
415 optimum.Price = curAnd1Price;
416 optimum.PosPrev = (UInt16)cur;
417 }
418 }
419 if (numDistancePairs == 0)
420 continue;
421 while (lenEnd < cur + newLen)
422 m_Optimum[++lenEnd].Price = kIfinityPrice;
423 UInt32 offs = 0;
424 UInt32 distance = matchDistances[(size_t)offs + 1];
425 curPrice += m_PosPrices[GetPosSlot(distance)];
426 for (UInt32 lenTest = kMatchMinLen; ; lenTest++)
427 {
428 UInt32 curAndLenPrice = curPrice + m_LenPrices[(size_t)lenTest - kMatchMinLen];
429 COptimal &optimum = m_Optimum[cur + lenTest];
430 if (curAndLenPrice < optimum.Price)
431 {
432 optimum.Price = curAndLenPrice;
433 optimum.PosPrev = (UInt16)cur;
434 optimum.BackPrev = (UInt16)distance;
435 }
436 if (lenTest == matchDistances[offs])
437 {
438 offs += 2;
439 if (offs == numDistancePairs)
440 break;
441 curPrice -= m_PosPrices[GetPosSlot(distance)];
442 distance = matchDistances[(size_t)offs + 1];
443 curPrice += m_PosPrices[GetPosSlot(distance)];
444 }
445 }
446 }
447 }
448
GetOptimalFast(UInt32 & backRes)449 UInt32 CCoder::GetOptimalFast(UInt32 &backRes)
450 {
451 GetMatches();
452 UInt32 numDistancePairs = m_MatchDistances[0];
453 if (numDistancePairs == 0)
454 return 1;
455 UInt32 lenMain = m_MatchDistances[(size_t)numDistancePairs - 1];
456 backRes = m_MatchDistances[numDistancePairs];
457 MovePos(lenMain - 1);
458 return lenMain;
459 }
460
InitStructures()461 void CTables::InitStructures()
462 {
463 UInt32 i;
464 for (i = 0; i < 256; i++)
465 litLenLevels[i] = 8;
466 litLenLevels[i++] = 13;
467 for (;i < kFixedMainTableSize; i++)
468 litLenLevels[i] = 5;
469 for (i = 0; i < kFixedDistTableSize; i++)
470 distLevels[i] = 5;
471 }
472
LevelTableDummy(const Byte * levels,unsigned numLevels,UInt32 * freqs)473 NO_INLINE void CCoder::LevelTableDummy(const Byte *levels, unsigned numLevels, UInt32 *freqs)
474 {
475 unsigned prevLen = 0xFF;
476 unsigned nextLen = levels[0];
477 unsigned count = 0;
478 unsigned maxCount = 7;
479 unsigned minCount = 4;
480
481 if (nextLen == 0)
482 {
483 maxCount = 138;
484 minCount = 3;
485 }
486
487 for (unsigned n = 0; n < numLevels; n++)
488 {
489 unsigned curLen = nextLen;
490 nextLen = (n < numLevels - 1) ? levels[(size_t)n + 1] : 0xFF;
491 count++;
492 if (count < maxCount && curLen == nextLen)
493 continue;
494
495 if (count < minCount)
496 freqs[curLen] += (UInt32)count;
497 else if (curLen != 0)
498 {
499 if (curLen != prevLen)
500 {
501 freqs[curLen]++;
502 count--;
503 }
504 freqs[kTableLevelRepNumber]++;
505 }
506 else if (count <= 10)
507 freqs[kTableLevel0Number]++;
508 else
509 freqs[kTableLevel0Number2]++;
510
511 count = 0;
512 prevLen = curLen;
513
514 if (nextLen == 0)
515 {
516 maxCount = 138;
517 minCount = 3;
518 }
519 else if (curLen == nextLen)
520 {
521 maxCount = 6;
522 minCount = 3;
523 }
524 else
525 {
526 maxCount = 7;
527 minCount = 4;
528 }
529 }
530 }
531
WriteBits(UInt32 value,unsigned numBits)532 NO_INLINE void CCoder::WriteBits(UInt32 value, unsigned numBits)
533 {
534 m_OutStream.WriteBits(value, numBits);
535 }
536
537 #define WRITE_HF2(codes, lens, i) m_OutStream.WriteBits(codes[i], lens[i])
538 #define WRITE_HF(i) WriteBits(codes[i], lens[i])
539
LevelTableCode(const Byte * levels,unsigned numLevels,const Byte * lens,const UInt32 * codes)540 NO_INLINE void CCoder::LevelTableCode(const Byte *levels, unsigned numLevels, const Byte *lens, const UInt32 *codes)
541 {
542 unsigned prevLen = 0xFF;
543 unsigned nextLen = levels[0];
544 unsigned count = 0;
545 unsigned maxCount = 7;
546 unsigned minCount = 4;
547
548 if (nextLen == 0)
549 {
550 maxCount = 138;
551 minCount = 3;
552 }
553
554 for (unsigned n = 0; n < numLevels; n++)
555 {
556 unsigned curLen = nextLen;
557 nextLen = (n < numLevels - 1) ? levels[(size_t)n + 1] : 0xFF;
558 count++;
559 if (count < maxCount && curLen == nextLen)
560 continue;
561
562 if (count < minCount)
563 for (unsigned i = 0; i < count; i++)
564 WRITE_HF(curLen);
565 else if (curLen != 0)
566 {
567 if (curLen != prevLen)
568 {
569 WRITE_HF(curLen);
570 count--;
571 }
572 WRITE_HF(kTableLevelRepNumber);
573 WriteBits(count - 3, 2);
574 }
575 else if (count <= 10)
576 {
577 WRITE_HF(kTableLevel0Number);
578 WriteBits(count - 3, 3);
579 }
580 else
581 {
582 WRITE_HF(kTableLevel0Number2);
583 WriteBits(count - 11, 7);
584 }
585
586 count = 0;
587 prevLen = curLen;
588
589 if (nextLen == 0)
590 {
591 maxCount = 138;
592 minCount = 3;
593 }
594 else if (curLen == nextLen)
595 {
596 maxCount = 6;
597 minCount = 3;
598 }
599 else
600 {
601 maxCount = 7;
602 minCount = 4;
603 }
604 }
605 }
606
MakeTables(unsigned maxHuffLen)607 NO_INLINE void CCoder::MakeTables(unsigned maxHuffLen)
608 {
609 Huffman_Generate(mainFreqs, mainCodes, m_NewLevels.litLenLevels, kFixedMainTableSize, maxHuffLen);
610 Huffman_Generate(distFreqs, distCodes, m_NewLevels.distLevels, kDistTableSize64, maxHuffLen);
611 }
612
Huffman_GetPrice(const UInt32 * freqs,const Byte * lens,UInt32 num)613 static NO_INLINE UInt32 Huffman_GetPrice(const UInt32 *freqs, const Byte *lens, UInt32 num)
614 {
615 UInt32 price = 0;
616 UInt32 i;
617 for (i = 0; i < num; i++)
618 price += lens[i] * freqs[i];
619 return price;
620 }
621
Huffman_GetPrice_Spec(const UInt32 * freqs,const Byte * lens,UInt32 num,const Byte * extraBits,UInt32 extraBase)622 static NO_INLINE UInt32 Huffman_GetPrice_Spec(const UInt32 *freqs, const Byte *lens, UInt32 num, const Byte *extraBits, UInt32 extraBase)
623 {
624 return Huffman_GetPrice(freqs, lens, num) +
625 Huffman_GetPrice(freqs + extraBase, extraBits, num - extraBase);
626 }
627
GetLzBlockPrice() const628 NO_INLINE UInt32 CCoder::GetLzBlockPrice() const
629 {
630 return
631 Huffman_GetPrice_Spec(mainFreqs, m_NewLevels.litLenLevels, kFixedMainTableSize, m_LenDirectBits, kSymbolMatch) +
632 Huffman_GetPrice_Spec(distFreqs, m_NewLevels.distLevels, kDistTableSize64, kDistDirectBits, 0);
633 }
634
TryBlock()635 NO_INLINE void CCoder::TryBlock()
636 {
637 memset(mainFreqs, 0, sizeof(mainFreqs));
638 memset(distFreqs, 0, sizeof(distFreqs));
639
640 m_ValueIndex = 0;
641 UInt32 blockSize = BlockSizeRes;
642 BlockSizeRes = 0;
643 for (;;)
644 {
645 if (m_OptimumCurrentIndex == m_OptimumEndIndex)
646 {
647 if (m_Pos >= kMatchArrayLimit
648 || BlockSizeRes >= blockSize
649 || (!m_SecondPass && ((Inline_MatchFinder_GetNumAvailableBytes(&_lzInWindow) == 0) || m_ValueIndex >= m_ValueBlockSize)))
650 break;
651 }
652 UInt32 pos;
653 UInt32 len;
654 if (_fastMode)
655 len = GetOptimalFast(pos);
656 else
657 len = GetOptimal(pos);
658 CCodeValue &codeValue = m_Values[m_ValueIndex++];
659 if (len >= kMatchMinLen)
660 {
661 UInt32 newLen = len - kMatchMinLen;
662 codeValue.Len = (UInt16)newLen;
663 mainFreqs[kSymbolMatch + (size_t)g_LenSlots[newLen]]++;
664 codeValue.Pos = (UInt16)pos;
665 distFreqs[GetPosSlot(pos)]++;
666 }
667 else
668 {
669 Byte b = *(Inline_MatchFinder_GetPointerToCurrentPos(&_lzInWindow) - m_AdditionalOffset);
670 mainFreqs[b]++;
671 codeValue.SetAsLiteral();
672 codeValue.Pos = b;
673 }
674 m_AdditionalOffset -= len;
675 BlockSizeRes += len;
676 }
677 mainFreqs[kSymbolEndOfBlock]++;
678 m_AdditionalOffset += BlockSizeRes;
679 m_SecondPass = true;
680 }
681
SetPrices(const CLevels & levels)682 NO_INLINE void CCoder::SetPrices(const CLevels &levels)
683 {
684 if (_fastMode)
685 return;
686 UInt32 i;
687 for (i = 0; i < 256; i++)
688 {
689 Byte price = levels.litLenLevels[i];
690 m_LiteralPrices[i] = ((price != 0) ? price : kNoLiteralStatPrice);
691 }
692
693 for (i = 0; i < m_NumLenCombinations; i++)
694 {
695 UInt32 slot = g_LenSlots[i];
696 Byte price = levels.litLenLevels[kSymbolMatch + (size_t)slot];
697 m_LenPrices[i] = (Byte)(((price != 0) ? price : kNoLenStatPrice) + m_LenDirectBits[slot]);
698 }
699
700 for (i = 0; i < kDistTableSize64; i++)
701 {
702 Byte price = levels.distLevels[i];
703 m_PosPrices[i] = (Byte)(((price != 0) ? price: kNoPosStatPrice) + kDistDirectBits[i]);
704 }
705 }
706
Huffman_ReverseBits(UInt32 * codes,const Byte * lens,UInt32 num)707 static NO_INLINE void Huffman_ReverseBits(UInt32 *codes, const Byte *lens, UInt32 num)
708 {
709 for (UInt32 i = 0; i < num; i++)
710 {
711 UInt32 x = codes[i];
712 x = ((x & 0x5555) << 1) | ((x & 0xAAAA) >> 1);
713 x = ((x & 0x3333) << 2) | ((x & 0xCCCC) >> 2);
714 x = ((x & 0x0F0F) << 4) | ((x & 0xF0F0) >> 4);
715 codes[i] = (((x & 0x00FF) << 8) | ((x & 0xFF00) >> 8)) >> (16 - lens[i]);
716 }
717 }
718
WriteBlock()719 NO_INLINE void CCoder::WriteBlock()
720 {
721 Huffman_ReverseBits(mainCodes, m_NewLevels.litLenLevels, kFixedMainTableSize);
722 Huffman_ReverseBits(distCodes, m_NewLevels.distLevels, kDistTableSize64);
723
724 for (UInt32 i = 0; i < m_ValueIndex; i++)
725 {
726 const CCodeValue &codeValue = m_Values[i];
727 if (codeValue.IsLiteral())
728 WRITE_HF2(mainCodes, m_NewLevels.litLenLevels, codeValue.Pos);
729 else
730 {
731 UInt32 len = codeValue.Len;
732 UInt32 lenSlot = g_LenSlots[len];
733 WRITE_HF2(mainCodes, m_NewLevels.litLenLevels, kSymbolMatch + lenSlot);
734 m_OutStream.WriteBits(len - m_LenStart[lenSlot], m_LenDirectBits[lenSlot]);
735 UInt32 dist = codeValue.Pos;
736 UInt32 posSlot = GetPosSlot(dist);
737 WRITE_HF2(distCodes, m_NewLevels.distLevels, posSlot);
738 m_OutStream.WriteBits(dist - kDistStart[posSlot], kDistDirectBits[posSlot]);
739 }
740 }
741 WRITE_HF2(mainCodes, m_NewLevels.litLenLevels, kSymbolEndOfBlock);
742 }
743
GetStorePrice(UInt32 blockSize,unsigned bitPosition)744 static UInt32 GetStorePrice(UInt32 blockSize, unsigned bitPosition)
745 {
746 UInt32 price = 0;
747 do
748 {
749 UInt32 nextBitPosition = (bitPosition + kFinalBlockFieldSize + kBlockTypeFieldSize) & 7;
750 unsigned numBitsForAlign = nextBitPosition > 0 ? (8 - nextBitPosition): 0;
751 UInt32 curBlockSize = (blockSize < (1 << 16)) ? blockSize : (1 << 16) - 1;
752 price += kFinalBlockFieldSize + kBlockTypeFieldSize + numBitsForAlign + (2 + 2) * 8 + curBlockSize * 8;
753 bitPosition = 0;
754 blockSize -= curBlockSize;
755 }
756 while (blockSize != 0);
757 return price;
758 }
759
WriteStoreBlock(UInt32 blockSize,UInt32 additionalOffset,bool finalBlock)760 void CCoder::WriteStoreBlock(UInt32 blockSize, UInt32 additionalOffset, bool finalBlock)
761 {
762 do
763 {
764 UInt32 curBlockSize = (blockSize < (1 << 16)) ? blockSize : (1 << 16) - 1;
765 blockSize -= curBlockSize;
766 WriteBits((finalBlock && (blockSize == 0) ? NFinalBlockField::kFinalBlock: NFinalBlockField::kNotFinalBlock), kFinalBlockFieldSize);
767 WriteBits(NBlockType::kStored, kBlockTypeFieldSize);
768 m_OutStream.FlushByte();
769 WriteBits((UInt16)curBlockSize, kStoredBlockLengthFieldSize);
770 WriteBits((UInt16)~curBlockSize, kStoredBlockLengthFieldSize);
771 const Byte *data = Inline_MatchFinder_GetPointerToCurrentPos(&_lzInWindow)- additionalOffset;
772 for (UInt32 i = 0; i < curBlockSize; i++)
773 m_OutStream.WriteByte(data[i]);
774 additionalOffset -= curBlockSize;
775 }
776 while (blockSize != 0);
777 }
778
TryDynBlock(unsigned tableIndex,UInt32 numPasses)779 NO_INLINE UInt32 CCoder::TryDynBlock(unsigned tableIndex, UInt32 numPasses)
780 {
781 CTables &t = m_Tables[tableIndex];
782 BlockSizeRes = t.BlockSizeRes;
783 UInt32 posTemp = t.m_Pos;
784 SetPrices(t);
785
786 for (UInt32 p = 0; p < numPasses; p++)
787 {
788 m_Pos = posTemp;
789 TryBlock();
790 unsigned numHuffBits =
791 (m_ValueIndex > 18000 ? 12 :
792 (m_ValueIndex > 7000 ? 11 :
793 (m_ValueIndex > 2000 ? 10 : 9)));
794 MakeTables(numHuffBits);
795 SetPrices(m_NewLevels);
796 }
797
798 (CLevels &)t = m_NewLevels;
799
800 m_NumLitLenLevels = kMainTableSize;
801 while (m_NumLitLenLevels > kNumLitLenCodesMin && m_NewLevels.litLenLevels[(size_t)m_NumLitLenLevels - 1] == 0)
802 m_NumLitLenLevels--;
803
804 m_NumDistLevels = kDistTableSize64;
805 while (m_NumDistLevels > kNumDistCodesMin && m_NewLevels.distLevels[(size_t)m_NumDistLevels - 1] == 0)
806 m_NumDistLevels--;
807
808 UInt32 levelFreqs[kLevelTableSize];
809 memset(levelFreqs, 0, sizeof(levelFreqs));
810
811 LevelTableDummy(m_NewLevels.litLenLevels, m_NumLitLenLevels, levelFreqs);
812 LevelTableDummy(m_NewLevels.distLevels, m_NumDistLevels, levelFreqs);
813
814 Huffman_Generate(levelFreqs, levelCodes, levelLens, kLevelTableSize, kMaxLevelBitLength);
815
816 m_NumLevelCodes = kNumLevelCodesMin;
817 for (UInt32 i = 0; i < kLevelTableSize; i++)
818 {
819 Byte level = levelLens[kCodeLengthAlphabetOrder[i]];
820 if (level > 0 && i >= m_NumLevelCodes)
821 m_NumLevelCodes = i + 1;
822 m_LevelLevels[i] = level;
823 }
824
825 return GetLzBlockPrice() +
826 Huffman_GetPrice_Spec(levelFreqs, levelLens, kLevelTableSize, kLevelDirectBits, kTableDirectLevels) +
827 kNumLenCodesFieldSize + kNumDistCodesFieldSize + kNumLevelCodesFieldSize +
828 m_NumLevelCodes * kLevelFieldSize + kFinalBlockFieldSize + kBlockTypeFieldSize;
829 }
830
TryFixedBlock(unsigned tableIndex)831 NO_INLINE UInt32 CCoder::TryFixedBlock(unsigned tableIndex)
832 {
833 CTables &t = m_Tables[tableIndex];
834 BlockSizeRes = t.BlockSizeRes;
835 m_Pos = t.m_Pos;
836 m_NewLevels.SetFixedLevels();
837 SetPrices(m_NewLevels);
838 TryBlock();
839 return kFinalBlockFieldSize + kBlockTypeFieldSize + GetLzBlockPrice();
840 }
841
GetBlockPrice(unsigned tableIndex,unsigned numDivPasses)842 NO_INLINE UInt32 CCoder::GetBlockPrice(unsigned tableIndex, unsigned numDivPasses)
843 {
844 CTables &t = m_Tables[tableIndex];
845 t.StaticMode = false;
846 UInt32 price = TryDynBlock(tableIndex, m_NumPasses);
847 t.BlockSizeRes = BlockSizeRes;
848 UInt32 numValues = m_ValueIndex;
849 UInt32 posTemp = m_Pos;
850 UInt32 additionalOffsetEnd = m_AdditionalOffset;
851
852 if (m_CheckStatic && m_ValueIndex <= kFixedHuffmanCodeBlockSizeMax)
853 {
854 const UInt32 fixedPrice = TryFixedBlock(tableIndex);
855 t.StaticMode = (fixedPrice < price);
856 if (t.StaticMode)
857 price = fixedPrice;
858 }
859
860 const UInt32 storePrice = GetStorePrice(BlockSizeRes, 0); // bitPosition
861 t.StoreMode = (storePrice <= price);
862 if (t.StoreMode)
863 price = storePrice;
864
865 t.UseSubBlocks = false;
866
867 if (numDivPasses > 1 && numValues >= kDivideCodeBlockSizeMin)
868 {
869 CTables &t0 = m_Tables[(tableIndex << 1)];
870 (CLevels &)t0 = t;
871 t0.BlockSizeRes = t.BlockSizeRes >> 1;
872 t0.m_Pos = t.m_Pos;
873 UInt32 subPrice = GetBlockPrice((tableIndex << 1), numDivPasses - 1);
874
875 UInt32 blockSize2 = t.BlockSizeRes - t0.BlockSizeRes;
876 if (t0.BlockSizeRes >= kDivideBlockSizeMin && blockSize2 >= kDivideBlockSizeMin)
877 {
878 CTables &t1 = m_Tables[(tableIndex << 1) + 1];
879 (CLevels &)t1 = t;
880 t1.BlockSizeRes = blockSize2;
881 t1.m_Pos = m_Pos;
882 m_AdditionalOffset -= t0.BlockSizeRes;
883 subPrice += GetBlockPrice((tableIndex << 1) + 1, numDivPasses - 1);
884 t.UseSubBlocks = (subPrice < price);
885 if (t.UseSubBlocks)
886 price = subPrice;
887 }
888 }
889
890 m_AdditionalOffset = additionalOffsetEnd;
891 m_Pos = posTemp;
892 return price;
893 }
894
CodeBlock(unsigned tableIndex,bool finalBlock)895 void CCoder::CodeBlock(unsigned tableIndex, bool finalBlock)
896 {
897 CTables &t = m_Tables[tableIndex];
898 if (t.UseSubBlocks)
899 {
900 CodeBlock((tableIndex << 1), false);
901 CodeBlock((tableIndex << 1) + 1, finalBlock);
902 }
903 else
904 {
905 if (t.StoreMode)
906 WriteStoreBlock(t.BlockSizeRes, m_AdditionalOffset, finalBlock);
907 else
908 {
909 WriteBits((finalBlock ? NFinalBlockField::kFinalBlock: NFinalBlockField::kNotFinalBlock), kFinalBlockFieldSize);
910 if (t.StaticMode)
911 {
912 WriteBits(NBlockType::kFixedHuffman, kBlockTypeFieldSize);
913 TryFixedBlock(tableIndex);
914 unsigned i;
915 const unsigned kMaxStaticHuffLen = 9;
916 for (i = 0; i < kFixedMainTableSize; i++)
917 mainFreqs[i] = (UInt32)1 << (kMaxStaticHuffLen - m_NewLevels.litLenLevels[i]);
918 for (i = 0; i < kFixedDistTableSize; i++)
919 distFreqs[i] = (UInt32)1 << (kMaxStaticHuffLen - m_NewLevels.distLevels[i]);
920 MakeTables(kMaxStaticHuffLen);
921 }
922 else
923 {
924 if (m_NumDivPasses > 1 || m_CheckStatic)
925 TryDynBlock(tableIndex, 1);
926 WriteBits(NBlockType::kDynamicHuffman, kBlockTypeFieldSize);
927 WriteBits(m_NumLitLenLevels - kNumLitLenCodesMin, kNumLenCodesFieldSize);
928 WriteBits(m_NumDistLevels - kNumDistCodesMin, kNumDistCodesFieldSize);
929 WriteBits(m_NumLevelCodes - kNumLevelCodesMin, kNumLevelCodesFieldSize);
930
931 for (UInt32 i = 0; i < m_NumLevelCodes; i++)
932 WriteBits(m_LevelLevels[i], kLevelFieldSize);
933
934 Huffman_ReverseBits(levelCodes, levelLens, kLevelTableSize);
935 LevelTableCode(m_NewLevels.litLenLevels, m_NumLitLenLevels, levelLens, levelCodes);
936 LevelTableCode(m_NewLevels.distLevels, m_NumDistLevels, levelLens, levelCodes);
937 }
938 WriteBlock();
939 }
940 m_AdditionalOffset -= t.BlockSizeRes;
941 }
942 }
943
944
CodeReal(ISequentialInStream * inStream,ISequentialOutStream * outStream,const UInt64 *,const UInt64 *,ICompressProgressInfo * progress)945 HRESULT CCoder::CodeReal(ISequentialInStream *inStream, ISequentialOutStream *outStream,
946 const UInt64 * /* inSize */ , const UInt64 * /* outSize */ , ICompressProgressInfo *progress)
947 {
948 m_CheckStatic = (m_NumPasses != 1 || m_NumDivPasses != 1);
949 m_IsMultiPass = (m_CheckStatic || (m_NumPasses != 1 || m_NumDivPasses != 1));
950
951 /* we can set stream mode before MatchFinder_Create
952 if default MatchFinder mode was not STREAM_MODE) */
953 // MatchFinder_SET_STREAM_MODE(&_lzInWindow);
954
955 CSeqInStreamWrap _seqInStream;
956 _seqInStream.Init(inStream);
957 MatchFinder_SET_STREAM(&_lzInWindow, &_seqInStream.vt)
958
959 RINOK(Create())
960
961 m_ValueBlockSize = (7 << 10) + (1 << 12) * m_NumDivPasses;
962
963 UInt64 nowPos = 0;
964
965 MatchFinder_Init(&_lzInWindow);
966 m_OutStream.SetStream(outStream);
967 m_OutStream.Init();
968
969 m_OptimumEndIndex = m_OptimumCurrentIndex = 0;
970
971 CTables &t = m_Tables[1];
972 t.m_Pos = 0;
973 t.InitStructures();
974
975 m_AdditionalOffset = 0;
976 do
977 {
978 t.BlockSizeRes = kBlockUncompressedSizeThreshold;
979 m_SecondPass = false;
980 GetBlockPrice(1, m_NumDivPasses);
981 CodeBlock(1, Inline_MatchFinder_GetNumAvailableBytes(&_lzInWindow) == 0);
982 nowPos += m_Tables[1].BlockSizeRes;
983 if (progress != NULL)
984 {
985 UInt64 packSize = m_OutStream.GetProcessedSize();
986 RINOK(progress->SetRatioInfo(&nowPos, &packSize))
987 }
988 }
989 while (Inline_MatchFinder_GetNumAvailableBytes(&_lzInWindow) != 0);
990
991 if (_seqInStream.Res != S_OK)
992 return _seqInStream.Res;
993
994 if (_lzInWindow.result != SZ_OK)
995 return SResToHRESULT(_lzInWindow.result);
996 return m_OutStream.Flush();
997 }
998
BaseCode(ISequentialInStream * inStream,ISequentialOutStream * outStream,const UInt64 * inSize,const UInt64 * outSize,ICompressProgressInfo * progress)999 HRESULT CCoder::BaseCode(ISequentialInStream *inStream, ISequentialOutStream *outStream,
1000 const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress)
1001 {
1002 try { return CodeReal(inStream, outStream, inSize, outSize, progress); }
1003 catch(const COutBufferException &e) { return e.ErrorCode; }
1004 catch(...) { return E_FAIL; }
1005 }
1006
Z7_COM7F_IMF(CCOMCoder::Code (ISequentialInStream * inStream,ISequentialOutStream * outStream,const UInt64 * inSize,const UInt64 * outSize,ICompressProgressInfo * progress))1007 Z7_COM7F_IMF(CCOMCoder::Code(ISequentialInStream *inStream, ISequentialOutStream *outStream,
1008 const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress))
1009 { return BaseCode(inStream, outStream, inSize, outSize, progress); }
1010
Z7_COM7F_IMF(CCOMCoder::SetCoderProperties (const PROPID * propIDs,const PROPVARIANT * props,UInt32 numProps))1011 Z7_COM7F_IMF(CCOMCoder::SetCoderProperties(const PROPID *propIDs, const PROPVARIANT *props, UInt32 numProps))
1012 { return BaseSetEncoderProperties2(propIDs, props, numProps); }
1013
Z7_COM7F_IMF(CCOMCoder64::Code (ISequentialInStream * inStream,ISequentialOutStream * outStream,const UInt64 * inSize,const UInt64 * outSize,ICompressProgressInfo * progress))1014 Z7_COM7F_IMF(CCOMCoder64::Code(ISequentialInStream *inStream, ISequentialOutStream *outStream,
1015 const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress))
1016 { return BaseCode(inStream, outStream, inSize, outSize, progress); }
1017
Z7_COM7F_IMF(CCOMCoder64::SetCoderProperties (const PROPID * propIDs,const PROPVARIANT * props,UInt32 numProps))1018 Z7_COM7F_IMF(CCOMCoder64::SetCoderProperties(const PROPID *propIDs, const PROPVARIANT *props, UInt32 numProps))
1019 { return BaseSetEncoderProperties2(propIDs, props, numProps); }
1020
1021 }}}
1022