1 #include "DeflateEncoder.h"
2 #include "Const.h"
3
4 #include "BinTree3ZMain.h"
5
6 namespace NDeflate {
7 namespace NEncoder {
8
9 static const int kValueBlockSize = 0x2000;
10
11 static const int kMaxCodeBitLength = 15;
12 static const int kMaxLevelBitLength = 7;
13
14 static const BYTE kFlagImm = 0;
15 static const BYTE kFlagLenPos = 4;
16
17 static const UINT32 kMaxUncompressedBlockSize = 0xFFFF; // test it !!!
18
19 static const UINT32 kBlockUncompressedSizeThreshold =
20 kMaxUncompressedBlockSize - kMatchMaxLen - kNumOpts;
21
22 static const int kNumGoodBacks = 0x10000;
23
24 static BYTE kNoLiteralDummy = 13;
25 static BYTE kNoLenDummy = 13;
26 static BYTE kNoPosDummy = 6;
27
28 static BYTE g_LenSlots[kNumLenCombinations];
29 static BYTE g_FastPos[1 << 8];
30
31 class CFastPosInit
32 {
33 public:
CFastPosInit()34 CFastPosInit()
35 {
36 unsigned i;
37 for(i = 0; i < kLenTableSize; i++)
38 {
39 int c = kLenStart[i];
40 int j = 1 << kLenDirectBits[i];
41 for(int k = 0; k < j; k++, c++)
42 g_LenSlots[c] = i;
43 }
44
45 const int kFastSlots = 16;
46 int c = 0;
47 for (BYTE aSlotFast = 0; aSlotFast < kFastSlots; aSlotFast++)
48 {
49 UINT32 k = (1 << kDistDirectBits[aSlotFast]);
50 for (UINT32 j = 0; j < k; j++, c++)
51 g_FastPos[c] = aSlotFast;
52 }
53 }
54 };
55
56 static CFastPosInit g_FastPosInit;
57
58
GetPosSlot(UINT32 aPos)59 inline UINT32 GetPosSlot(UINT32 aPos)
60 {
61 // for (UINT32 i = 1; aPos >= kDistStart[i]; i++);
62 // return i - 1;
63 if (aPos < 0x100)
64 return g_FastPos[aPos];
65 return g_FastPos[aPos >> 7] + 14;
66 }
67
CCoder()68 CCoder::CCoder():
69 m_MainCoder(kMainTableSize, kLenDirectBits, kMatchNumber, kMaxCodeBitLength),
70 m_DistCoder(kDistTableSize, kDistDirectBits, 0, kMaxCodeBitLength),
71 m_LevelCoder(kLevelTableSize, kLevelDirectBits, 0, kMaxLevelBitLength),
72 m_NumPasses(1),
73 m_NumFastBytes(32),
74 m_OnePosMatchesMemory(0),
75 m_OnePosMatchesArray(0),
76 m_MatchDistances(0),
77 m_Created(false),
78 m_Values(0)
79 {
80 m_Values = new CCodeValue[kValueBlockSize + kNumOpts];
81 }
82
Create()83 HRESULT CCoder::Create()
84 {
85 m_MatchFinder.Create(kHistorySize, kNumOpts + kNumGoodBacks, m_NumFastBytes,
86 kMatchMaxLen - m_NumFastBytes);
87 m_MatchLengthEdge = m_NumFastBytes + 1;
88
89 if (m_NumPasses > 1)
90 {
91 m_OnePosMatchesMemory = new UINT16[kNumGoodBacks * (m_NumFastBytes + 1)];
92 try
93 {
94 m_OnePosMatchesArray = new COnePosMatches[kNumGoodBacks];
95 }
96 catch(...)
97 {
98 delete []m_OnePosMatchesMemory;
99 m_OnePosMatchesMemory = 0;
100 throw;
101 }
102 UINT16 *aGoodBacksWordsCurrent = m_OnePosMatchesMemory;
103 for(int i = 0; i < kNumGoodBacks; i++, aGoodBacksWordsCurrent += (m_NumFastBytes + 1))
104 m_OnePosMatchesArray[i].Init(aGoodBacksWordsCurrent);
105 }
106 else
107 m_MatchDistances = new UINT16[m_NumFastBytes + 1];
108 return S_OK;
109 }
110
SetEncoderNumPasses(UINT32 A)111 HRESULT CCoder::SetEncoderNumPasses(UINT32 A) {
112 m_NumPasses = A;
113 if (m_NumPasses == 0 || m_NumPasses > 255)
114 return E_INVALIDARG;
115 return S_OK;
116 }
117
SetEncoderNumFastBytes(UINT32 A)118 HRESULT CCoder::SetEncoderNumFastBytes(UINT32 A) {
119 m_NumFastBytes = A;
120 if(m_NumFastBytes < 3 || m_NumFastBytes > kMatchMaxLen)
121 return E_INVALIDARG;
122 return S_OK;
123 }
124
Free()125 void CCoder::Free()
126 {
127 if(m_NumPasses > 0)
128 {
129 if (m_NumPasses > 1)
130 {
131 delete []m_OnePosMatchesMemory;
132 delete []m_OnePosMatchesArray;
133 }
134 else
135 delete []m_MatchDistances;
136 }
137 }
138
~CCoder()139 CCoder::~CCoder()
140 {
141 Free();
142 delete []m_Values;
143 }
144
ReadGoodBacks()145 void CCoder::ReadGoodBacks()
146 {
147 UINT32 aGoodIndex;
148 if (m_NumPasses > 1)
149 {
150 aGoodIndex = m_FinderPos % kNumGoodBacks;
151 m_MatchDistances = m_OnePosMatchesArray[aGoodIndex].MatchDistances;
152 }
153 UINT32 aDistanceTmp[kMatchMaxLen + 1];
154 UINT32 aLen = m_MatchFinder.GetLongestMatch(aDistanceTmp);
155 for(UINT32 i = kMatchMinLen; i <= aLen; i++)
156 m_MatchDistances[i] = aDistanceTmp[i];
157
158 m_LongestMatchDistance = m_MatchDistances[aLen];
159 if (aLen == m_NumFastBytes && m_NumFastBytes != kMatchMaxLen)
160 m_LongestMatchLength = aLen + m_MatchFinder.GetMatchLen(aLen,
161 m_LongestMatchDistance, kMatchMaxLen - aLen);
162 else
163 m_LongestMatchLength = aLen;
164 if (m_NumPasses > 1)
165 {
166 m_OnePosMatchesArray[aGoodIndex].LongestMatchDistance = UINT16(m_LongestMatchDistance);
167 m_OnePosMatchesArray[aGoodIndex].LongestMatchLength = UINT16(m_LongestMatchLength);
168 }
169 HRESULT aResult = m_MatchFinder.MovePos();
170 if (aResult != S_OK)
171 throw aResult;
172 m_FinderPos++;
173 m_AdditionalOffset++;
174 }
175
GetBacks(UINT32 aPos)176 void CCoder::GetBacks(UINT32 aPos)
177 {
178 if(aPos == m_FinderPos)
179 ReadGoodBacks();
180 else
181 {
182 if (m_NumPasses == 1)
183 {
184 if(aPos + 1 == m_FinderPos)
185 return;
186 throw E_INTERNAL_ERROR;
187 }
188 else
189 {
190 UINT32 aGoodIndex = aPos % kNumGoodBacks;
191 m_MatchDistances = m_OnePosMatchesArray[aGoodIndex].MatchDistances;
192 m_LongestMatchDistance = m_OnePosMatchesArray[aGoodIndex].LongestMatchDistance;
193 m_LongestMatchLength = m_OnePosMatchesArray[aGoodIndex].LongestMatchLength;
194 }
195 }
196 }
197
198
MovePos(UINT32 aNum)199 void CCoder::MovePos(UINT32 aNum)
200 {
201 if (m_NumPasses > 1)
202 {
203 for(UINT32 i = 0; i < aNum; i++)
204 GetBacks(UINT32(m_BlockStartPostion + m_CurrentBlockUncompressedSize + i + 1));
205 }
206 else
207 {
208 for (;aNum > 0; aNum--)
209 {
210 m_MatchFinder.DummyLongestMatch();
211 HRESULT aResult = m_MatchFinder.MovePos();
212 if (aResult != S_OK)
213 throw aResult;
214 m_FinderPos++;
215 m_AdditionalOffset++;
216 }
217 }
218 }
219
220 static const int kIfinityPrice = 0xFFFFFFF;
221
Backward(UINT32 & aBackRes,UINT32 aCur)222 UINT32 CCoder::Backward(UINT32 &aBackRes, UINT32 aCur)
223 {
224 m_OptimumEndIndex = aCur;
225 UINT32 aPosMem = m_Optimum[aCur].PosPrev;
226 UINT16 aBackMem = m_Optimum[aCur].BackPrev;
227 do
228 {
229 UINT32 aPosPrev = aPosMem;
230 UINT16 aBackCur = aBackMem;
231 aBackMem = m_Optimum[aPosPrev].BackPrev;
232 aPosMem = m_Optimum[aPosPrev].PosPrev;
233 m_Optimum[aPosPrev].BackPrev = aBackCur;
234 m_Optimum[aPosPrev].PosPrev = aCur;
235 aCur = aPosPrev;
236 }
237 while(aCur > 0);
238 aBackRes = m_Optimum[0].BackPrev;
239 m_OptimumCurrentIndex = m_Optimum[0].PosPrev;
240 return m_OptimumCurrentIndex;
241 }
242
GetOptimal(UINT32 & aBackRes)243 UINT32 CCoder::GetOptimal(UINT32 &aBackRes)
244 {
245 if(m_OptimumEndIndex != m_OptimumCurrentIndex)
246 {
247 UINT32 aLen = m_Optimum[m_OptimumCurrentIndex].PosPrev - m_OptimumCurrentIndex;
248 aBackRes = m_Optimum[m_OptimumCurrentIndex].BackPrev;
249 m_OptimumCurrentIndex = m_Optimum[m_OptimumCurrentIndex].PosPrev;
250 return aLen;
251 }
252 m_OptimumCurrentIndex = 0;
253 m_OptimumEndIndex = 0;
254
255 GetBacks(UINT32(m_BlockStartPostion + m_CurrentBlockUncompressedSize));
256
257 UINT32 aLenMain = m_LongestMatchLength;
258 UINT32 aBackMain = m_LongestMatchDistance;
259
260 if(aLenMain < kMatchMinLen)
261 return 1;
262 if(aLenMain >= m_MatchLengthEdge)
263 {
264 aBackRes = aBackMain;
265 MovePos(aLenMain - 1);
266 return aLenMain;
267 }
268 m_Optimum[1].Price = m_LiteralPrices[m_MatchFinder.GetIndexByte(0 - m_AdditionalOffset)];
269 m_Optimum[1].PosPrev = 0;
270
271 m_Optimum[2].Price = kIfinityPrice;
272 m_Optimum[2].PosPrev = 1;
273
274 for(UINT32 i = kMatchMinLen; i <= aLenMain; i++)
275 {
276 m_Optimum[i].PosPrev = 0;
277 m_Optimum[i].BackPrev = m_MatchDistances[i];
278 m_Optimum[i].Price = m_LenPrices[i - kMatchMinLen] + m_PosPrices[GetPosSlot(m_MatchDistances[i])];
279 }
280
281
282 UINT32 aCur = 0;
283 UINT32 aLenEnd = aLenMain;
284 while(true)
285 {
286 aCur++;
287 if(aCur == aLenEnd)
288 return Backward(aBackRes, aCur);
289 GetBacks(UINT32(m_BlockStartPostion + m_CurrentBlockUncompressedSize + aCur));
290 UINT32 aNewLen = m_LongestMatchLength;
291 if(aNewLen >= m_MatchLengthEdge)
292 return Backward(aBackRes, aCur);
293
294 UINT32 aCurPrice = m_Optimum[aCur].Price;
295 UINT32 aCurAnd1Price = aCurPrice +
296 m_LiteralPrices[m_MatchFinder.GetIndexByte(aCur - m_AdditionalOffset)];
297 COptimal &anOptimum = m_Optimum[aCur + 1];
298 if (aCurAnd1Price < anOptimum.Price)
299 {
300 anOptimum.Price = aCurAnd1Price;
301 anOptimum.PosPrev = aCur;
302 }
303 if (aNewLen < kMatchMinLen)
304 continue;
305 if(aCur + aNewLen > aLenEnd)
306 {
307 if (aCur + aNewLen > kNumOpts - 1)
308 aNewLen = kNumOpts - 1 - aCur;
309 UINT32 aLenEndNew = aCur + aNewLen;
310 if (aLenEnd < aLenEndNew)
311 {
312 for(UINT32 i = aLenEnd + 1; i <= aLenEndNew; i++)
313 m_Optimum[i].Price = kIfinityPrice;
314 aLenEnd = aLenEndNew;
315 }
316 }
317 for(UINT32 aLenTest = kMatchMinLen; aLenTest <= aNewLen; aLenTest++)
318 {
319 UINT16 aCurBack = m_MatchDistances[aLenTest];
320 UINT32 aCurAndLenPrice = aCurPrice +
321 m_LenPrices[aLenTest - kMatchMinLen] + m_PosPrices[GetPosSlot(aCurBack)];
322 COptimal &anOptimum = m_Optimum[aCur + aLenTest];
323 if (aCurAndLenPrice < anOptimum.Price)
324 {
325 anOptimum.Price = aCurAndLenPrice;
326 anOptimum.PosPrev = aCur;
327 anOptimum.BackPrev = aCurBack;
328 }
329 }
330 }
331 }
332
333
InitStructures()334 void CCoder::InitStructures()
335 {
336 memset(m_LastLevels, 0, kMaxTableSize);
337
338 m_ValueIndex = 0;
339 m_OptimumEndIndex = 0;
340 m_OptimumCurrentIndex = 0;
341 m_AdditionalOffset = 0;
342
343 m_BlockStartPostion = 0;
344 m_CurrentBlockUncompressedSize = 0;
345
346 m_MainCoder.StartNewBlock();
347 m_DistCoder.StartNewBlock();
348
349 unsigned i;
350 for(i = 0; i < 256; i++)
351 m_LiteralPrices[i] = 8;
352 for(i = 0; i < kNumLenCombinations; i++)
353 m_LenPrices[i] = 5 + kLenDirectBits[g_LenSlots[i]]; // test it
354 for(i = 0; i < kDistTableSize; i++)
355 m_PosPrices[i] = 5 + kDistDirectBits[i];
356 }
357
WriteBlockData(bool aWriteMode,bool anFinalBlock)358 void CCoder::WriteBlockData(bool aWriteMode, bool anFinalBlock)
359 {
360 m_MainCoder.AddSymbol(kReadTableNumber);
361 int aMethod = WriteTables(aWriteMode, anFinalBlock);
362
363 if (aWriteMode)
364 {
365 if(aMethod == NBlockType::kStored)
366 {
367 for(UINT32 i = 0; i < m_CurrentBlockUncompressedSize; i++)
368 {
369 BYTE aByte = m_MatchFinder.GetIndexByte(i - m_AdditionalOffset -
370 m_CurrentBlockUncompressedSize);
371 m_OutStream.WriteBits(aByte, 8);
372 }
373 }
374 else
375 {
376 for (UINT32 i = 0; i < m_ValueIndex; i++)
377 {
378 if (m_Values[i].Flag == kFlagImm)
379 m_MainCoder.CodeOneValue(&m_ReverseOutStream, m_Values[i].Imm);
380 else if (m_Values[i].Flag == kFlagLenPos)
381 {
382 UINT32 aLen = m_Values[i].Len;
383 UINT32 aLenSlot = g_LenSlots[aLen];
384 m_MainCoder.CodeOneValue(&m_ReverseOutStream, kMatchNumber + aLenSlot);
385 m_OutStream.WriteBits(aLen - kLenStart[aLenSlot], kLenDirectBits[aLenSlot]);
386 UINT32 aDist = m_Values[i].Pos;
387 UINT32 aPosSlot = GetPosSlot(aDist);
388 m_DistCoder.CodeOneValue(&m_ReverseOutStream, aPosSlot);
389 m_OutStream.WriteBits(aDist - kDistStart[aPosSlot], kDistDirectBits[aPosSlot]);
390 }
391 }
392 m_MainCoder.CodeOneValue(&m_ReverseOutStream, kReadTableNumber);
393 }
394 }
395 m_MainCoder.StartNewBlock();
396 m_DistCoder.StartNewBlock();
397 m_ValueIndex = 0;
398 UINT32 i;
399 for(i = 0; i < 256; i++)
400 if(m_LastLevels[i] != 0)
401 m_LiteralPrices[i] = m_LastLevels[i];
402 else
403 m_LiteralPrices[i] = kNoLiteralDummy;
404
405 // -------------- Normal match -----------------------------
406
407 for(i = 0; i < kNumLenCombinations; i++)
408 {
409 UINT32 aSlot = g_LenSlots[i];
410 BYTE aDummy = m_LastLevels[kMatchNumber + aSlot];
411 if (aDummy != 0)
412 m_LenPrices[i] = aDummy;
413 else
414 m_LenPrices[i] = kNoLenDummy;
415 m_LenPrices[i] += kLenDirectBits[aSlot];
416 }
417 for(i = 0; i < kDistTableSize; i++)
418 {
419 BYTE aDummy = m_LastLevels[kDistTableStart + i];
420 if (aDummy != 0)
421 m_PosPrices[i] = aDummy;
422 else
423 m_PosPrices[i] = kNoPosDummy;
424 m_PosPrices[i] += kDistDirectBits[i];
425 }
426 }
427
CodeLevelTable(BYTE * aNewLevels,int aNumLevels,bool aCodeMode)428 void CCoder::CodeLevelTable(BYTE *aNewLevels, int aNumLevels, bool aCodeMode)
429 {
430 int aPrevLen = 0xFF; // last emitted length
431 int aNextLen = aNewLevels[0]; // length of next code
432 int aCount = 0; // repeat aCount of the current code
433 int aMaxCount = 7; // max repeat aCount
434 int aMinCount = 4; // min repeat aCount
435 if (aNextLen == 0)
436 {
437 aMaxCount = 138;
438 aMinCount = 3;
439 }
440 BYTE anOldValueInGuardElement = aNewLevels[aNumLevels]; // push guard value
441 try
442 {
443 aNewLevels[aNumLevels] = 0xFF; // guard already set
444 for (int n = 0; n < aNumLevels; n++)
445 {
446 int aCurLen = aNextLen;
447 aNextLen = aNewLevels[n + 1];
448 aCount++;
449 if (aCount < aMaxCount && aCurLen == aNextLen)
450 continue;
451 else if (aCount < aMinCount)
452 for(int i = 0; i < aCount; i++)
453 {
454 int aCodeLen = aCurLen;
455 if (aCodeMode)
456 m_LevelCoder.CodeOneValue(&m_ReverseOutStream, aCodeLen);
457 else
458 m_LevelCoder.AddSymbol(aCodeLen);
459 }
460 else if (aCurLen != 0)
461 {
462 if (aCurLen != aPrevLen)
463 {
464 int aCodeLen = aCurLen;
465 if (aCodeMode)
466 m_LevelCoder.CodeOneValue(&m_ReverseOutStream, aCodeLen);
467 else
468 m_LevelCoder.AddSymbol(aCodeLen);
469 aCount--;
470 }
471 if (aCodeMode)
472 {
473 m_LevelCoder.CodeOneValue(&m_ReverseOutStream, kTableLevelRepNumber);
474 m_OutStream.WriteBits(aCount - 3, 2);
475 }
476 else
477 m_LevelCoder.AddSymbol(kTableLevelRepNumber);
478 }
479 else if (aCount <= 10)
480 {
481 if (aCodeMode)
482 {
483 m_LevelCoder.CodeOneValue(&m_ReverseOutStream, kTableLevel0Number);
484 m_OutStream.WriteBits(aCount - 3, 3);
485 }
486 else
487 m_LevelCoder.AddSymbol(kTableLevel0Number);
488 }
489 else
490 {
491 if (aCodeMode)
492 {
493 m_LevelCoder.CodeOneValue(&m_ReverseOutStream, kTableLevel0Number2);
494 m_OutStream.WriteBits(aCount - 11, 7);
495 }
496 else
497 m_LevelCoder.AddSymbol(kTableLevel0Number2);
498 }
499 aCount = 0;
500 aPrevLen = aCurLen;
501 if (aNextLen == 0)
502 {
503 aMaxCount = 138;
504 aMinCount = 3;
505 }
506 else if (aCurLen == aNextLen)
507 {
508 aMaxCount = 6;
509 aMinCount = 3;
510 }
511 else
512 {
513 aMaxCount = 7;
514 aMinCount = 4;
515 }
516 }
517 }
518 catch(...)
519 {
520 aNewLevels[aNumLevels] = anOldValueInGuardElement; // old guard
521 throw;
522 }
523 aNewLevels[aNumLevels] = anOldValueInGuardElement; // old guard
524 }
525
WriteTables(bool aWriteMode,bool anFinalBlock)526 int CCoder::WriteTables(bool aWriteMode, bool anFinalBlock)
527 {
528 BYTE aNewLevels[kMaxTableSize + 1]; // (+ 1) for guard
529
530 m_MainCoder.BuildTree(&aNewLevels[0]);
531 m_DistCoder.BuildTree(&aNewLevels[kDistTableStart]);
532
533
534 memset(m_LastLevels, 0, kMaxTableSize);
535
536 if (aWriteMode)
537 {
538 if(anFinalBlock)
539 m_OutStream.WriteBits(NFinalBlockField::kFinalBlock, kFinalBlockFieldSize);
540 else
541 m_OutStream.WriteBits(NFinalBlockField::kNotFinalBlock, kFinalBlockFieldSize);
542
543 m_LevelCoder.StartNewBlock();
544
545 int aNumLitLenLevels = kMainTableSize;
546 while(aNumLitLenLevels > kDeflateNumberOfLitLenCodesMin && aNewLevels[aNumLitLenLevels - 1] == 0)
547 aNumLitLenLevels--;
548
549 int aNumDistLevels = kDistTableSize;
550 while(aNumDistLevels > kDeflateNumberOfDistanceCodesMin &&
551 aNewLevels[kDistTableStart + aNumDistLevels - 1] == 0)
552 aNumDistLevels--;
553
554
555 /////////////////////////
556 // First Pass
557
558 CodeLevelTable(aNewLevels, aNumLitLenLevels, false);
559 CodeLevelTable(&aNewLevels[kDistTableStart], aNumDistLevels, false);
560
561 memcpy(m_LastLevels, aNewLevels, kMaxTableSize);
562
563
564 BYTE aLevelLevels[kLevelTableSize];
565 m_LevelCoder.BuildTree(aLevelLevels);
566
567 BYTE aLevelLevelsStream[kLevelTableSize];
568 int aNumLevelCodes = kDeflateNumberOfLevelCodesMin;
569 int i;
570 for (i = 0; i < kLevelTableSize; i++)
571 {
572 int aStreamPos = kCodeLengthAlphabetOrder[i];
573 int aLevel = aLevelLevels[aStreamPos];
574 if (aLevel > 0 && i >= aNumLevelCodes)
575 aNumLevelCodes = i + 1;
576 aLevelLevelsStream[i] = aLevel;
577 }
578
579 UINT32 aNumLZHuffmanBits = m_MainCoder.GetBlockBitLength();
580 aNumLZHuffmanBits += m_DistCoder.GetBlockBitLength();
581 aNumLZHuffmanBits += m_LevelCoder.GetBlockBitLength();
582 aNumLZHuffmanBits += kDeflateNumberOfLengthCodesFieldSize +
583 kDeflateNumberOfDistanceCodesFieldSize +
584 kDeflateNumberOfLevelCodesFieldSize;
585 aNumLZHuffmanBits += aNumLevelCodes * kDeflateLevelCodeFieldSize;
586
587 UINT32 aNextBitPosition =
588 (m_OutStream.GetBitPosition() + kBlockTypeFieldSize) % 8;
589 UINT32 aNumBitsForAlign = aNextBitPosition > 0 ? (8 - aNextBitPosition): 0;
590
591 UINT32 aNumStoreBits = aNumBitsForAlign + (2 * sizeof(UINT16)) * 8;
592 aNumStoreBits += m_CurrentBlockUncompressedSize * 8;
593 if(aNumStoreBits < aNumLZHuffmanBits)
594 {
595 m_OutStream.WriteBits(NBlockType::kStored, kBlockTypeFieldSize); // test it
596 m_OutStream.WriteBits(0, aNumBitsForAlign); // test it
597 UINT16 aCurrentBlockUncompressedSize = UINT16(m_CurrentBlockUncompressedSize);
598 UINT16 aCurrentBlockUncompressedSizeNot = ~aCurrentBlockUncompressedSize;
599 m_OutStream.WriteBits(aCurrentBlockUncompressedSize, kDeflateStoredBlockLengthFieldSizeSize);
600 m_OutStream.WriteBits(aCurrentBlockUncompressedSizeNot, kDeflateStoredBlockLengthFieldSizeSize);
601 return NBlockType::kStored;
602 }
603 else
604 {
605 m_OutStream.WriteBits(NBlockType::kDynamicHuffman, kBlockTypeFieldSize);
606 m_OutStream.WriteBits(aNumLitLenLevels - kDeflateNumberOfLitLenCodesMin, kDeflateNumberOfLengthCodesFieldSize);
607 m_OutStream.WriteBits(aNumDistLevels - kDeflateNumberOfDistanceCodesMin,
608 kDeflateNumberOfDistanceCodesFieldSize);
609 m_OutStream.WriteBits(aNumLevelCodes - kDeflateNumberOfLevelCodesMin,
610 kDeflateNumberOfLevelCodesFieldSize);
611
612 for (i = 0; i < aNumLevelCodes; i++)
613 m_OutStream.WriteBits(aLevelLevelsStream[i], kDeflateLevelCodeFieldSize);
614
615 /////////////////////////
616 // Second Pass
617
618 CodeLevelTable(aNewLevels, aNumLitLenLevels, true);
619 CodeLevelTable(&aNewLevels[kDistTableStart], aNumDistLevels, true);
620 return NBlockType::kDynamicHuffman;
621 }
622 }
623 else
624 memcpy(m_LastLevels, aNewLevels, kMaxTableSize);
625 return -1;
626 }
627
CodeReal(ISequentialInStream * anInStream,ISequentialOutStream * anOutStream,const UINT64 * anInSize)628 HRESULT CCoder::CodeReal(ISequentialInStream *anInStream, ISequentialOutStream *anOutStream, const UINT64 *anInSize)
629 {
630 if (!m_Created)
631 {
632 RETURN_IF_NOT_S_OK(Create());
633 m_Created = true;
634 }
635
636 UINT64 aNowPos = 0;
637 m_FinderPos = 0;
638
639 RETURN_IF_NOT_S_OK(m_MatchFinder.Init(anInStream));
640 m_OutStream.Init(anOutStream);
641 m_ReverseOutStream.Init(&m_OutStream);
642
643 InitStructures();
644
645 while(true)
646 {
647 int aCurrentPassIndex = 0;
648 bool aNoMoreBytes;
649 while (true)
650 {
651 while(true)
652 {
653 aNoMoreBytes = (m_AdditionalOffset == 0 && m_MatchFinder.GetNumAvailableBytes() == 0);
654
655 if (((m_CurrentBlockUncompressedSize >= kBlockUncompressedSizeThreshold ||
656 m_ValueIndex >= kValueBlockSize) &&
657 (m_OptimumEndIndex == m_OptimumCurrentIndex))
658 || aNoMoreBytes)
659 break;
660 UINT32 aPos;
661 UINT32 aLen = GetOptimal(aPos);
662 if (aLen >= kMatchMinLen)
663 {
664 UINT32 aNewLen = aLen - kMatchMinLen;
665 m_Values[m_ValueIndex].Flag = kFlagLenPos;
666 m_Values[m_ValueIndex].Len = BYTE(aNewLen);
667 UINT32 aLenSlot = g_LenSlots[aNewLen];
668 m_MainCoder.AddSymbol(kMatchNumber + aLenSlot);
669 m_Values[m_ValueIndex].Pos = UINT16(aPos);
670 UINT32 aPosSlot = GetPosSlot(aPos);
671 m_DistCoder.AddSymbol(aPosSlot);
672 }
673 else if (aLen == 1)
674 {
675 BYTE aByte = m_MatchFinder.GetIndexByte(0 - m_AdditionalOffset);
676 aLen = 1;
677 m_MainCoder.AddSymbol(aByte);
678 m_Values[m_ValueIndex].Flag = kFlagImm;
679 m_Values[m_ValueIndex].Imm = aByte;
680 }
681 else
682 throw E_INTERNAL_ERROR;
683 m_ValueIndex++;
684 m_AdditionalOffset -= aLen;
685 aNowPos += aLen;
686 m_CurrentBlockUncompressedSize += aLen;
687
688 }
689 aCurrentPassIndex++;
690 bool aWriteMode = (aCurrentPassIndex == m_NumPasses);
691 WriteBlockData(aWriteMode, aNoMoreBytes);
692 if (aWriteMode)
693 break;
694 aNowPos = m_BlockStartPostion;
695 m_AdditionalOffset = UINT32(m_FinderPos - m_BlockStartPostion);
696 m_CurrentBlockUncompressedSize = 0;
697 }
698 m_BlockStartPostion += m_CurrentBlockUncompressedSize;
699 m_CurrentBlockUncompressedSize = 0;
700 if (aNoMoreBytes)
701 break;
702 }
703 return m_OutStream.Flush();
704 }
705
Code(ISequentialInStream * anInStream,ISequentialOutStream * anOutStream,const UINT64 * anInSize)706 HRESULT CCoder::Code(ISequentialInStream *anInStream,ISequentialOutStream *anOutStream, const UINT64 *anInSize)
707 {
708 try {
709 return CodeReal(anInStream, anOutStream, anInSize);
710 } catch (HRESULT& e) {
711 return e;
712 } catch (...) {
713 return E_FAIL;
714 }
715 }
716
717 }}
718