?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
BCM WL 6.30.102.9 (r366174)
[tomato.git] / release / src-rt / linux / linux-2.6 / scripts / squashfs / lzma / CS / 7zip / Compress / LZMA / LzmaEncoder.cs
blobf9daa60fb990be4f801f17e78afc53b0938dc7f0
1 // LzmaEncoder.cs
2
3 using System;
4
5 namespace SevenZip.Compression.LZMA
6 {
7 using RangeCoder;
8
9 public class Encoder : ICoder, ISetCoderProperties, IWriteCoderProperties
10 {
11 enum EMatchFinderType
12 {
13 BT2,
14 BT4,
15 BT4B
16 };
17
18 static string[] kMatchFinderIDs =
19 {
20 "BT2",
21 "BT4",
22 "BT4B",
23 };
24
25 static int FindMatchFinder(string s)
26 {
27 for (int m = 0; m < kMatchFinderIDs.Length; m++)
28 if (s == kMatchFinderIDs[m])
29 return m;
30 return -1;
31 }
32
33 const UInt32 kIfinityPrice = 0xFFFFFFF;
34
35 static Byte[] g_FastPos = new Byte[1024];
36
37 static Encoder()
38 {
39 const Byte kFastSlots = 20;
40 int c = 2;
41 g_FastPos[0] = 0;
42 g_FastPos[1] = 1;
43 for (Byte slotFast = 2; slotFast < kFastSlots; slotFast++)
44 {
45 UInt32 k = ((UInt32)1 << ((slotFast >> 1) - 1));
46 for (UInt32 j = 0; j < k; j++, c++)
47 g_FastPos[c] = slotFast;
48 }
49 }
50
51 static UInt32 GetPosSlot(UInt32 pos)
52 {
53 if (pos < (1 << 10))
54 return g_FastPos[pos];
55 if (pos < (1 << 19))
56 return (UInt32)(g_FastPos[pos >> 9] + 18);
57 return (UInt32)(g_FastPos[pos >> 18] + 36);
58 }
59
60 static UInt32 GetPosSlot2(UInt32 pos)
61 {
62 if (pos < (1 << 16))
63 return (UInt32)(g_FastPos[pos >> 6] + 12);
64 if (pos < (1 << 25))
65 return (UInt32)(g_FastPos[pos >> 15] + 30);
66 return (UInt32)(g_FastPos[pos >> 24] + 48);
67 }
68
69 Base.State _state = new Base.State();
70 Byte _previousByte;
71 UInt32[] _repDistances = new UInt32[Base.kNumRepDistances];
72
73 void BaseInit()
74 {
75 _state.Init();
76 _previousByte = 0;
77 for (UInt32 i = 0; i < Base.kNumRepDistances; i++)
78 _repDistances[i] = 0;
79 }
80
81 const int kDefaultDictionaryLogSize = 20;
82 const UInt32 kNumFastBytesDefault = 0x20;
83
84 class LiteralEncoder
85 {
86 public struct Encoder2
87 {
88 BitEncoder[] m_Encoders;
89
90 public void Create() { m_Encoders = new BitEncoder[0x300]; }
91
92 public void Init() { for (int i = 0; i < 0x300; i++) m_Encoders[i].Init(); }
93
94 public void Encode(RangeCoder.Encoder rangeEncoder, byte symbol)
95 {
96 uint context = 1;
97 for (int i = 7; i >= 0; i--)
98 {
99 uint bit = (uint)((symbol >> i) & 1);
100 m_Encoders[context].Encode(rangeEncoder, bit);
101 context = (context << 1) | bit;
102 }
103 }
104
105 public void EncodeMatched(RangeCoder.Encoder rangeEncoder, byte matchByte, byte symbol)
106 {
107 uint context = 1;
108 bool same = true;
109 for (int i = 7; i >= 0; i--)
110 {
111 uint bit = (uint)((symbol >> i) & 1);
112 uint state = context;
113 if (same)
114 {
115 uint matchBit = (uint)((matchByte >> i) & 1);
116 state += ((1 + matchBit) << 8);
117 same = (matchBit == bit);
118 }
119 m_Encoders[state].Encode(rangeEncoder, bit);
120 context = (context << 1) | bit;
121 }
122 }
123
124 public uint GetPrice(bool matchMode, byte matchByte, byte symbol)
125 {
126 uint price = 0;
127 uint context = 1;
128 int i = 7;
129 if (matchMode)
130 {
131 for (; i >= 0; i--)
132 {
133 uint matchBit = (uint)(matchByte >> i) & 1;
134 uint bit = (uint)(symbol >> i) & 1;
135 price += m_Encoders[((1 + matchBit) << 8) + context].GetPrice(bit);
136 context = (context << 1) | bit;
137 if (matchBit != bit)
138 {
139 i--;
140 break;
141 }
142 }
143 }
144 for (; i >= 0; i--)
145 {
146 uint bit = (uint)(symbol >> i) & 1;
147 price += m_Encoders[context].GetPrice(bit);
148 context = (context << 1) | bit;
149 }
150 return price;
151 }
152 }
153
154 Encoder2[] m_Coders;
155 int m_NumPrevBits;
156 int m_NumPosBits;
157 uint m_PosMask;
158
159 public void Create(int numPosBits, int numPrevBits)
160 {
161 if (m_Coders != null && m_NumPrevBits == numPrevBits &&
162 m_NumPosBits == numPosBits)
163 return;
164 m_NumPosBits = numPosBits;
165 m_PosMask = ((uint)1 << numPosBits) - 1;
166 m_NumPrevBits = numPrevBits;
167 uint numStates = (uint)1 << (m_NumPrevBits + m_NumPosBits);
168 m_Coders = new Encoder2[numStates];
169 for (uint i = 0; i < numStates; i++)
170 m_Coders[i].Create();
171 }
172
173 public void Init()
174 {
175 uint numStates = (uint)1 << (m_NumPrevBits + m_NumPosBits);
176 for (uint i = 0; i < numStates; i++)
177 m_Coders[i].Init();
178 }
179
180 uint GetState(uint pos, byte prevByte)
181 { return ((pos & m_PosMask) << m_NumPrevBits) + (uint)(prevByte >> (8 - m_NumPrevBits)); }
182
183 public Encoder2 GetSubCoder(UInt32 pos, Byte prevByte)
184 { return m_Coders[GetState(pos, prevByte)]; }
185 }
186
187 class LenEncoder
188 {
189 RangeCoder.BitEncoder _choice = new RangeCoder.BitEncoder();
190 RangeCoder.BitEncoder _choice2 = new RangeCoder.BitEncoder();
191 RangeCoder.BitTreeEncoder[] _lowCoder = new RangeCoder.BitTreeEncoder[Base.kNumPosStatesEncodingMax]; // kNumLowBits
192 RangeCoder.BitTreeEncoder[] _midCoder = new RangeCoder.BitTreeEncoder[Base.kNumPosStatesEncodingMax]; // kNumMidBits
193 RangeCoder.BitTreeEncoder _highCoder = new RangeCoder.BitTreeEncoder(Base.kNumHighLenBits);
194
195 public LenEncoder()
196 {
197 for (UInt32 posState = 0; posState < Base.kNumPosStatesEncodingMax; posState++)
198 {
199 _lowCoder[posState] = new RangeCoder.BitTreeEncoder(Base.kNumLowLenBits);
200 _midCoder[posState] = new RangeCoder.BitTreeEncoder(Base.kNumMidLenBits);
201 }
202 }
203
204 public void Init(UInt32 numPosStates)
205 {
206 _choice.Init();
207 _choice2.Init();
208 for (UInt32 posState = 0; posState < numPosStates; posState++)
209 {
210 _lowCoder[posState].Init();
211 _midCoder[posState].Init();
212 }
213 _highCoder.Init();
214 }
215
216 public void Encode(RangeCoder.Encoder rangeEncoder, UInt32 symbol, UInt32 posState)
217 {
218 if (symbol < Base.kNumLowLenSymbols)
219 {
220 _choice.Encode(rangeEncoder, 0);
221 _lowCoder[posState].Encode(rangeEncoder, symbol);
222 }
223 else
224 {
225 symbol -= Base.kNumLowLenSymbols;
226 _choice.Encode(rangeEncoder, 1);
227 if (symbol < Base.kNumMidLenSymbols)
228 {
229 _choice2.Encode(rangeEncoder, 0);
230 _midCoder[posState].Encode(rangeEncoder, symbol);
231 }
232 else
233 {
234 _choice2.Encode(rangeEncoder, 1);
235 _highCoder.Encode(rangeEncoder, symbol - Base.kNumMidLenSymbols);
236 }
237 }
238 }
239
240 public UInt32 GetPrice(UInt32 symbol, UInt32 posState)
241 {
242 UInt32 price = 0;
243 if (symbol < Base.kNumLowLenSymbols)
244 {
245 price += _choice.GetPrice0();
246 price += _lowCoder[posState].GetPrice(symbol);
247 }
248 else
249 {
250 symbol -= Base.kNumLowLenSymbols;
251 price += _choice.GetPrice1();
252 if (symbol < Base.kNumMidLenSymbols)
253 {
254 price += _choice2.GetPrice0();
255 price += _midCoder[posState].GetPrice(symbol);
256 }
257 else
258 {
259 price += _choice2.GetPrice1();
260 price += _highCoder.GetPrice(symbol - Base.kNumMidLenSymbols);
261 }
262 }
263 return price;
264 }
265 };
266
267 const UInt32 kNumLenSpecSymbols = Base.kNumLowLenSymbols + Base.kNumMidLenSymbols;
268
269 class LenPriceTableEncoder : LenEncoder
270 {
271 UInt32[] _prices = new UInt32[Base.kNumLenSymbols << Base.kNumPosStatesBitsEncodingMax];
272 UInt32 _tableSize;
273 UInt32[] _counters = new UInt32[Base.kNumPosStatesEncodingMax];
274
275 public void SetTableSize(UInt32 tableSize) { _tableSize = tableSize; }
276
277 public new UInt32 GetPrice(UInt32 symbol, UInt32 posState)
278 {
279 return _prices[(symbol << Base.kNumPosStatesBitsEncodingMax) + posState];
280 }
281
282 void UpdateTable(UInt32 posState)
283 {
284 for (UInt32 len = 0; len < _tableSize; len++)
285 _prices[(len << Base.kNumPosStatesBitsEncodingMax) + posState] = base.GetPrice(len, posState);
286 _counters[posState] = _tableSize;
287 }
288
289 public void UpdateTables(UInt32 numPosStates)
290 {
291 for (UInt32 posState = 0; posState < numPosStates; posState++)
292 UpdateTable(posState);
293 }
294
295 public new void Encode(RangeCoder.Encoder rangeEncoder, UInt32 symbol, UInt32 posState)
296 {
297 base.Encode(rangeEncoder, symbol, posState);
298 if (--_counters[posState] == 0)
299 UpdateTable(posState);
300 }
301 }
302
303 const UInt32 kNumOpts = 1 << 12;
304 class Optimal
305 {
306 public Base.State State;
307
308 public bool Prev1IsChar;
309 public bool Prev2;
310
311 public UInt32 PosPrev2;
312 public UInt32 BackPrev2;
313
314 public UInt32 Price;
315 public UInt32 PosPrev; // posNext;
316 public UInt32 BackPrev;
317
318 // public UInt32 []Backs = new UInt32[Base.kNumRepDistances];
319 public UInt32 Backs0;
320 public UInt32 Backs1;
321 public UInt32 Backs2;
322 public UInt32 Backs3;
323
324 public void MakeAsChar() { BackPrev = 0xFFFFFFFF; Prev1IsChar = false; }
325 public void MakeAsShortRep() { BackPrev = 0; ; Prev1IsChar = false; }
326 public bool IsShortRep() { return (BackPrev == 0); }
327 };
328 Optimal[] _optimum = new Optimal[kNumOpts];
329
330 LZ.IMatchFinder _matchFinder = null; // test it
331 RangeCoder.Encoder _rangeEncoder = new RangeCoder.Encoder();
332
333 RangeCoder.BitEncoder[] _isMatch = new RangeCoder.BitEncoder[Base.kNumStates << Base.kNumPosStatesBitsMax];
334 RangeCoder.BitEncoder[] _isRep = new RangeCoder.BitEncoder[Base.kNumStates];
335 RangeCoder.BitEncoder[] _isRepG0 = new RangeCoder.BitEncoder[Base.kNumStates];
336 RangeCoder.BitEncoder[] _isRepG1 = new RangeCoder.BitEncoder[Base.kNumStates];
337 RangeCoder.BitEncoder[] _isRepG2 = new RangeCoder.BitEncoder[Base.kNumStates];
338 RangeCoder.BitEncoder[] _isRep0Long = new RangeCoder.BitEncoder[Base.kNumStates << Base.kNumPosStatesBitsMax];
339
340 RangeCoder.BitTreeEncoder[] _posSlotEncoder = new RangeCoder.BitTreeEncoder[Base.kNumLenToPosStates]; // kNumPosSlotBits
341 RangeCoder.BitEncoder[] _posEncoders = new RangeCoder.BitEncoder[Base.kNumFullDistances - Base.kEndPosModelIndex];
342 RangeCoder.BitTreeEncoder _posAlignEncoder = new RangeCoder.BitTreeEncoder(Base.kNumAlignBits);
343
344 LenPriceTableEncoder _lenEncoder = new LenPriceTableEncoder();
345 LenPriceTableEncoder _repMatchLenEncoder = new LenPriceTableEncoder();
346
347 LiteralEncoder _literalEncoder = new LiteralEncoder();
348
349 UInt32[] _matchDistances = new UInt32[Base.kMatchMaxLen + 1];
350 bool _fastMode = false;
351 bool _maxMode = false;
352 UInt32 _numFastBytes = kNumFastBytesDefault;
353 UInt32 _longestMatchLength;
354 UInt32 _additionalOffset;
355
356 UInt32 _optimumEndIndex;
357 UInt32 _optimumCurrentIndex;
358
359 bool _longestMatchWasFound;
360
361 UInt32[] _posSlotPrices = new UInt32[Base.kDistTableSizeMax << Base.kNumLenToPosStatesBits];
362 UInt32[] _distancesPrices = new UInt32[Base.kNumFullDistances << Base.kNumLenToPosStatesBits];
363 UInt32[] _alignPrices = new UInt32[Base.kAlignTableSize];
364 UInt32 _alignPriceCount;
365
366 UInt32 _distTableSize = (kDefaultDictionaryLogSize * 2);
367
368 int _posStateBits = 2;
369 UInt32 _posStateMask = (4 - 1);
370 int _numLiteralPosStateBits = 0;
371 int _numLiteralContextBits = 3;
372
373 UInt32 _dictionarySize = (1 << kDefaultDictionaryLogSize);
374 UInt32 _dictionarySizePrev = 0xFFFFFFFF;
375 UInt32 _numFastBytesPrev = 0xFFFFFFFF;
376
377 Int64 lastPosSlotFillingPos;
378 Int64 nowPos64;
379 bool _finished;
380
381 System.IO.Stream _inStream;
382 EMatchFinderType _matchFinderType = EMatchFinderType.BT4;
383 bool _writeEndMark;
384 bool _needReleaseMFStream;
385
386 void Create()
387 {
388 // _rangeEncoder.Create(1 << 20);
389 if (_matchFinder == null)
390 {
391 LZ.BinTree bt = new LZ.BinTree();
392 int numHashBytes = 4;
393 bool big = false;
394 switch (_matchFinderType)
395 {
396 case EMatchFinderType.BT2:
397 numHashBytes = 2;
398 break;
399 case EMatchFinderType.BT4:
400 break;
401 case EMatchFinderType.BT4B:
402 big = true;
403 break;
404 }
405 bt.SetType(numHashBytes, big);
406 _matchFinder = bt;
407 }
408 _literalEncoder.Create(_numLiteralPosStateBits, _numLiteralContextBits);
409
410 if (_dictionarySize == _dictionarySizePrev && _numFastBytesPrev == _numFastBytes)
411 return;
412 _matchFinder.Create(_dictionarySize, kNumOpts, _numFastBytes,
413 Base.kMatchMaxLen * 2 + 1 - _numFastBytes);
414 _dictionarySizePrev = _dictionarySize;
415 _numFastBytesPrev = _numFastBytes;
416 }
417
418 public Encoder()
419 {
420 for (int i = 0; i < kNumOpts; i++)
421 _optimum[i] = new Optimal();
422 for (int i = 0; i < Base.kNumLenToPosStates; i++)
423 _posSlotEncoder[i] = new RangeCoder.BitTreeEncoder(Base.kNumPosSlotBits);
424 }
425
426 void SetWriteEndMarkerMode(bool writeEndMarker)
427 {
428 _writeEndMark = writeEndMarker;
429 }
430 void Init()
431 {
432 BaseInit();
433 _rangeEncoder.Init();
434
435 uint i;
436 for (i = 0; i < Base.kNumStates; i++)
437 {
438 for (uint j = 0; j <= _posStateMask; j++)
439 {
440 uint complexState = (i << Base.kNumPosStatesBitsMax) + j;
441 _isMatch[complexState].Init();
442 _isRep0Long[complexState].Init();
443 }
444 _isRep[i].Init();
445 _isRepG0[i].Init();
446 _isRepG1[i].Init();
447 _isRepG2[i].Init();
448 }
449 _literalEncoder.Init();
450 for (i = 0; i < Base.kNumLenToPosStates; i++)
451 _posSlotEncoder[i].Init();
452 for (i = 0; i < Base.kNumFullDistances - Base.kEndPosModelIndex; i++)
453 _posEncoders[i].Init();
454
455 _lenEncoder.Init((UInt32)1 << _posStateBits);
456 _repMatchLenEncoder.Init((UInt32)1 << _posStateBits);
457
458 _posAlignEncoder.Init();
459
460 _longestMatchWasFound = false;
461 _optimumEndIndex = 0;
462 _optimumCurrentIndex = 0;
463 _additionalOffset = 0;
464 }
465
466 void ReadMatchDistances(out UInt32 lenRes)
467 {
468 lenRes = _matchFinder.GetLongestMatch(_matchDistances);
469 if (lenRes == _numFastBytes)
470 lenRes += _matchFinder.GetMatchLen((int)lenRes, _matchDistances[lenRes],
471 Base.kMatchMaxLen - lenRes);
472 _additionalOffset++;
473 _matchFinder.MovePos();
474 }
475
476 void MovePos(UInt32 num)
477 {
478 for (; num > 0; num--)
479 {
480 _matchFinder.DummyLongestMatch();
481 _matchFinder.MovePos();
482 _additionalOffset++;
483 }
484 }
485
486 UInt32 GetRepLen1Price(Base.State state, UInt32 posState)
487 {
488 return _isRepG0[state.Index].GetPrice0() +
489 _isRep0Long[(state.Index << Base.kNumPosStatesBitsMax) + posState].GetPrice0();
490 }
491
492 UInt32 GetRepPrice(UInt32 repIndex, UInt32 len, Base.State state, UInt32 posState)
493 {
494 UInt32 price = _repMatchLenEncoder.GetPrice(len - Base.kMatchMinLen, posState);
495 if (repIndex == 0)
496 {
497 price += _isRepG0[state.Index].GetPrice0();
498 price += _isRep0Long[(state.Index << Base.kNumPosStatesBitsMax) + posState].GetPrice1();
499 }
500 else
501 {
502 price += _isRepG0[state.Index].GetPrice1();
503 if (repIndex == 1)
504 price += _isRepG1[state.Index].GetPrice0();
505 else
506 {
507 price += _isRepG1[state.Index].GetPrice1();
508 price += _isRepG2[state.Index].GetPrice(repIndex - 2);
509 }
510 }
511 return price;
512 }
513
514 UInt32 GetPosLenPrice(UInt32 pos, UInt32 len, UInt32 posState)
515 {
516 if (len == 2 && pos >= 0x80)
517 return kIfinityPrice;
518 UInt32 price;
519 UInt32 lenToPosState = Base.GetLenToPosState(len);
520 if (pos < Base.kNumFullDistances)
521 price = _distancesPrices[(pos << Base.kNumLenToPosStatesBits) + lenToPosState];
522 else
523 price = _posSlotPrices[(GetPosSlot2(pos) << Base.kNumLenToPosStatesBits) + lenToPosState] +
524 _alignPrices[pos & Base.kAlignMask];
525 return price + _lenEncoder.GetPrice(len - Base.kMatchMinLen, posState);
526 }
527
528 UInt32 Backward(out UInt32 backRes, UInt32 cur)
529 {
530 _optimumEndIndex = cur;
531 UInt32 posMem = _optimum[cur].PosPrev;
532 UInt32 backMem = _optimum[cur].BackPrev;
533 do
534 {
535 if (_optimum[cur].Prev1IsChar)
536 {
537 _optimum[posMem].MakeAsChar();
538 _optimum[posMem].PosPrev = posMem - 1;
539 if (_optimum[cur].Prev2)
540 {
541 _optimum[posMem - 1].Prev1IsChar = false;
542 _optimum[posMem - 1].PosPrev = _optimum[cur].PosPrev2;
543 _optimum[posMem - 1].BackPrev = _optimum[cur].BackPrev2;
544 }
545 }
546 UInt32 posPrev = posMem;
547 UInt32 backCur = backMem;
548
549 backMem = _optimum[posPrev].BackPrev;
550 posMem = _optimum[posPrev].PosPrev;
551
552 _optimum[posPrev].BackPrev = backCur;
553 _optimum[posPrev].PosPrev = cur;
554 cur = posPrev;
555 }
556 while (cur > 0);
557 backRes = _optimum[0].BackPrev;
558 _optimumCurrentIndex = _optimum[0].PosPrev;
559 return _optimumCurrentIndex;
560 }
561
562
563 UInt32[] reps = new UInt32[Base.kNumRepDistances];
564 UInt32[] repLens = new UInt32[Base.kNumRepDistances];
565
566 UInt32 GetOptimum(UInt32 position, out UInt32 backRes)
567 {
568 if (_optimumEndIndex != _optimumCurrentIndex)
569 {
570 UInt32 lenRes = _optimum[_optimumCurrentIndex].PosPrev - _optimumCurrentIndex;
571 backRes = _optimum[_optimumCurrentIndex].BackPrev;
572 _optimumCurrentIndex = _optimum[_optimumCurrentIndex].PosPrev;
573 return lenRes;
574 }
575 _optimumCurrentIndex = 0;
576 _optimumEndIndex = 0; // test it;
577
578 UInt32 lenMain;
579 if (!_longestMatchWasFound)
580 {
581 ReadMatchDistances(out lenMain);
582 }
583 else
584 {
585 lenMain = _longestMatchLength;
586 _longestMatchWasFound = false;
587 }
588
589 UInt32 repMaxIndex = 0;
590 UInt32 i;
591 for (i = 0; i < Base.kNumRepDistances; i++)
592 {
593 reps[i] = _repDistances[i];
594 repLens[i] = _matchFinder.GetMatchLen(0 - 1, reps[i], Base.kMatchMaxLen);
595 if (i == 0 || repLens[i] > repLens[repMaxIndex])
596 repMaxIndex = i;
597 }
598 if (repLens[repMaxIndex] >= _numFastBytes)
599 {
600 backRes = repMaxIndex;
601 UInt32 lenRes = repLens[repMaxIndex];
602 MovePos(lenRes - 1);
603 return lenRes;
604 }
605
606 if (lenMain >= _numFastBytes)
607 {
608 UInt32 backMain = (lenMain < _numFastBytes) ? _matchDistances[lenMain] :
609 _matchDistances[_numFastBytes];
610 backRes = backMain + Base.kNumRepDistances;
611 MovePos(lenMain - 1);
612 return lenMain;
613 }
614 Byte currentByte = _matchFinder.GetIndexByte(0 - 1);
615
616 _optimum[0].State = _state;
617
618 Byte matchByte;
619
620 matchByte = _matchFinder.GetIndexByte((Int32)(0 - _repDistances[0] - 1 - 1));
621
622 UInt32 posState = (position & _posStateMask);
623
624 _optimum[1].Price = _isMatch[(_state.Index << Base.kNumPosStatesBitsMax) + posState].GetPrice0() +
625 _literalEncoder.GetSubCoder(position, _previousByte).GetPrice(!_state.IsCharState(), matchByte, currentByte);
626 _optimum[1].MakeAsChar();
627
628 _optimum[1].PosPrev = 0;
629
630 _optimum[0].Backs0 = reps[0];
631 _optimum[0].Backs1 = reps[1];
632 _optimum[0].Backs2 = reps[2];
633 _optimum[0].Backs3 = reps[3];
634
635
636 UInt32 matchPrice = _isMatch[(_state.Index << Base.kNumPosStatesBitsMax) + posState].GetPrice1();
637 UInt32 repMatchPrice = matchPrice + _isRep[_state.Index].GetPrice1();
638
639 if (matchByte == currentByte)
640 {
641 UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(_state, posState);
642 if (shortRepPrice < _optimum[1].Price)
643 {
644 _optimum[1].Price = shortRepPrice;
645 _optimum[1].MakeAsShortRep();
646 }
647 }
648 if (lenMain < 2)
649 {
650 backRes = _optimum[1].BackPrev;
651 return 1;
652 }
653
654
655 UInt32 normalMatchPrice = matchPrice + _isRep[_state.Index].GetPrice0();
656
657 if (lenMain <= repLens[repMaxIndex])
658 lenMain = 0;
659
660 UInt32 len;
661 for (len = 2; len <= lenMain; len++)
662 {
663 _optimum[len].PosPrev = 0;
664 _optimum[len].BackPrev = _matchDistances[len] + Base.kNumRepDistances;
665 _optimum[len].Price = normalMatchPrice +
666 GetPosLenPrice(_matchDistances[len], len, posState);
667 _optimum[len].Prev1IsChar = false;
668 }
669
670 if (lenMain < repLens[repMaxIndex])
671 lenMain = repLens[repMaxIndex];
672
673 for (; len <= lenMain; len++)
674 _optimum[len].Price = kIfinityPrice;
675
676 for (i = 0; i < Base.kNumRepDistances; i++)
677 {
678 UInt32 repLen = repLens[i];
679 for (UInt32 lenTest = 2; lenTest <= repLen; lenTest++)
680 {
681 UInt32 curAndLenPrice = repMatchPrice + GetRepPrice(i, lenTest, _state, posState);
682 Optimal optimum = _optimum[lenTest];
683 if (curAndLenPrice < optimum.Price)
684 {
685 optimum.Price = curAndLenPrice;
686 optimum.PosPrev = 0;
687 optimum.BackPrev = i;
688 optimum.Prev1IsChar = false;
689 }
690 }
691 }
692
693 UInt32 cur = 0;
694 UInt32 lenEnd = lenMain;
695
696 while (true)
697 {
698 cur++;
699 if (cur == lenEnd)
700 {
701 return Backward(out backRes, cur);
702 }
703 position++;
704 UInt32 posPrev = _optimum[cur].PosPrev;
705 Base.State state;
706 if (_optimum[cur].Prev1IsChar)
707 {
708 posPrev--;
709 if (_optimum[cur].Prev2)
710 {
711 state = _optimum[_optimum[cur].PosPrev2].State;
712 if (_optimum[cur].BackPrev2 < Base.kNumRepDistances)
713 state.UpdateRep();
714 else
715 state.UpdateMatch();
716 }
717 else
718 state = _optimum[posPrev].State;
719 state.UpdateChar();
720 }
721 else
722 state = _optimum[posPrev].State;
723 if (posPrev == cur - 1)
724 {
725 if (_optimum[cur].IsShortRep())
726 state.UpdateShortRep();
727 else
728 state.UpdateChar();
729 }
730 else
731 {
732 UInt32 pos;
733 if (_optimum[cur].Prev1IsChar && _optimum[cur].Prev2)
734 {
735 posPrev = _optimum[cur].PosPrev2;
736 pos = _optimum[cur].BackPrev2;
737 state.UpdateRep();
738 }
739 else
740 {
741 pos = _optimum[cur].BackPrev;
742 if (pos < Base.kNumRepDistances)
743 state.UpdateRep();
744 else
745 state.UpdateMatch();
746 }
747 Optimal opt = _optimum[posPrev];
748 if (pos < Base.kNumRepDistances)
749 {
750 if (pos == 0)
751 {
752 reps[0] = opt.Backs0;
753 reps[1] = opt.Backs1;
754 reps[2] = opt.Backs2;
755 reps[3] = opt.Backs3;
756 }
757 else if (pos == 1)
758 {
759 reps[0] = opt.Backs1;
760 reps[1] = opt.Backs0;
761 reps[2] = opt.Backs2;
762 reps[3] = opt.Backs3;
763 }
764 else if (pos == 2)
765 {
766 reps[0] = opt.Backs2;
767 reps[1] = opt.Backs0;
768 reps[2] = opt.Backs1;
769 reps[3] = opt.Backs3;
770 }
771 else
772 {
773 reps[0] = opt.Backs3;
774 reps[1] = opt.Backs0;
775 reps[2] = opt.Backs1;
776 reps[3] = opt.Backs2;
777 }
778 }
779 else
780 {
781 reps[0] = (pos - Base.kNumRepDistances);
782 reps[1] = opt.Backs0;
783 reps[2] = opt.Backs1;
784 reps[3] = opt.Backs2;
785 }
786 }
787 _optimum[cur].State = state;
788 _optimum[cur].Backs0 = reps[0];
789 _optimum[cur].Backs1 = reps[1];
790 _optimum[cur].Backs2 = reps[2];
791 _optimum[cur].Backs3 = reps[3];
792 UInt32 newLen;
793 ReadMatchDistances(out newLen);
794 if (newLen >= _numFastBytes)
795 {
796 _longestMatchLength = newLen;
797 _longestMatchWasFound = true;
798 return Backward(out backRes, cur);
799 }
800 UInt32 curPrice = _optimum[cur].Price;
801
802 currentByte = _matchFinder.GetIndexByte(0 - 1);
803 matchByte = _matchFinder.GetIndexByte((Int32)(0 - reps[0] - 1 - 1));
804
805 posState = (position & _posStateMask);
806
807 UInt32 curAnd1Price = curPrice +
808 _isMatch[(state.Index << Base.kNumPosStatesBitsMax) + posState].GetPrice0() +
809 _literalEncoder.GetSubCoder(position, _matchFinder.GetIndexByte(0 - 2)).
810 GetPrice(!state.IsCharState(), matchByte, currentByte);
811
812 Optimal nextOptimum = _optimum[cur + 1];
813
814 bool nextIsChar = false;
815 if (curAnd1Price < nextOptimum.Price)
816 {
817 nextOptimum.Price = curAnd1Price;
818 nextOptimum.PosPrev = cur;
819 nextOptimum.MakeAsChar();
820 nextIsChar = true;
821 }
822
823 matchPrice = curPrice + _isMatch[(state.Index << Base.kNumPosStatesBitsMax) + posState].GetPrice1();
824 repMatchPrice = matchPrice + _isRep[state.Index].GetPrice1();
825
826 if (matchByte == currentByte &&
827 !(nextOptimum.PosPrev < cur && nextOptimum.BackPrev == 0))
828 {
829 UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(state, posState);
830 if (shortRepPrice <= nextOptimum.Price)
831 {
832 nextOptimum.Price = shortRepPrice;
833 nextOptimum.PosPrev = cur;
834 nextOptimum.MakeAsShortRep();
835 // nextIsChar = false;
836 }
837 }
838 /*
839 if(newLen == 2 && _matchDistances[2] >= kDistLimit2) // test it maybe set 2000 ?
840 continue;
841 */
842
843 UInt32 numAvailableBytesFull = _matchFinder.GetNumAvailableBytes() + 1;
844 numAvailableBytesFull = Math.Min(kNumOpts - 1 - cur, numAvailableBytesFull);
845 UInt32 numAvailableBytes = numAvailableBytesFull;
846
847 if (numAvailableBytes < 2)
848 continue;
849 if (numAvailableBytes > _numFastBytes)
850 numAvailableBytes = _numFastBytes;
851 if (numAvailableBytes >= 3 && !nextIsChar)
852 {
853 UInt32 backOffset = reps[0] + 1;
854 UInt32 temp;
855 for (temp = 1; temp < numAvailableBytes; temp++)
856 // if (data[temp] != data[(size_t)temp - backOffset])
857 if (_matchFinder.GetIndexByte((Int32)temp - 1) != _matchFinder.GetIndexByte((Int32)temp - (Int32)backOffset - 1))
858 break;
859 UInt32 lenTest2 = temp - 1;
860 if (lenTest2 >= 2)
861 {
862 Base.State state2 = state;
863 state2.UpdateChar();
864 UInt32 posStateNext = (position + 1) & _posStateMask;
865 UInt32 nextRepMatchPrice = curAnd1Price +
866 _isMatch[(state2.Index << Base.kNumPosStatesBitsMax) + posStateNext].GetPrice1() +
867 _isRep[state2.Index].GetPrice1();
868 // for (; lenTest2 >= 2; lenTest2--)
869 {
870 while (lenEnd < cur + 1 + lenTest2)
871 _optimum[++lenEnd].Price = kIfinityPrice;
872 UInt32 curAndLenPrice = nextRepMatchPrice + GetRepPrice(
873 0, lenTest2, state2, posStateNext);
874 Optimal optimum = _optimum[cur + 1 + lenTest2];
875 if (curAndLenPrice < optimum.Price)
876 {
877 optimum.Price = curAndLenPrice;
878 optimum.PosPrev = cur + 1;
879 optimum.BackPrev = 0;
880 optimum.Prev1IsChar = true;
881 optimum.Prev2 = false;
882 }
883 }
884 }
885 }
886 for (UInt32 repIndex = 0; repIndex < Base.kNumRepDistances; repIndex++)
887 {
888 // UInt32 repLen = _matchFinder->GetMatchLen(0 - 1, reps[repIndex], newLen); // test it;
889 UInt32 backOffset = reps[repIndex] + 1;
890 if (_matchFinder.GetIndexByte(-1) !=
891 _matchFinder.GetIndexByte((Int32)(-1 - (Int32)backOffset)) ||
892 _matchFinder.GetIndexByte(0) !=
893 _matchFinder.GetIndexByte((Int32)(0 - (Int32)backOffset)))
894 continue;
895 UInt32 lenTest;
896 for (lenTest = 2; lenTest < numAvailableBytes; lenTest++)
897 if (_matchFinder.GetIndexByte((Int32)lenTest - 1) !=
898 _matchFinder.GetIndexByte((Int32)lenTest - 1 - (Int32)backOffset))
899 break;
900 UInt32 lenTestTemp = lenTest;
901 do
902 {
903 while (lenEnd < cur + lenTest)
904 _optimum[++lenEnd].Price = kIfinityPrice;
905 UInt32 curAndLenPrice = repMatchPrice + GetRepPrice(repIndex, lenTest, state, posState);
906 Optimal optimum = _optimum[cur + lenTest];
907 if (curAndLenPrice < optimum.Price)
908 {
909 optimum.Price = curAndLenPrice;
910 optimum.PosPrev = cur;
911 optimum.BackPrev = repIndex;
912 optimum.Prev1IsChar = false;
913 }
914 }
915 while(--lenTest >= 2);
916 lenTest = lenTestTemp;
917
918 if (_maxMode)
919 {
920 UInt32 lenTest2 = lenTest + 1;
921 UInt32 limit = Math.Min(numAvailableBytesFull, lenTest2 + _numFastBytes);
922 for (; lenTest2 < limit; lenTest2++)
923 if (_matchFinder.GetIndexByte((Int32)((Int32)lenTest2 - 1)) !=
924 _matchFinder.GetIndexByte((Int32)((Int32)lenTest2 - 1 - (Int32)backOffset)))
925 break;
926 lenTest2 -= lenTest + 1;
927 if (lenTest2 >= 2)
928 {
929 Base.State state2 = state;
930 state2.UpdateRep();
931 UInt32 posStateNext = (position + lenTest) & _posStateMask;
932 UInt32 curAndLenCharPrice =
933 repMatchPrice + GetRepPrice(repIndex, lenTest, state, posState) +
934 _isMatch[(state2.Index << Base.kNumPosStatesBitsMax) + posStateNext].GetPrice0() +
935 _literalEncoder.GetSubCoder(position + lenTest,
936 _matchFinder.GetIndexByte((Int32)lenTest - 1 - 1)).GetPrice(true,
937 _matchFinder.GetIndexByte((Int32)((Int32)lenTest - 1 - (Int32)backOffset)),
938 _matchFinder.GetIndexByte((Int32)lenTest - 1));
939 state2.UpdateChar();
940 posStateNext = (position + lenTest + 1) & _posStateMask;
941 UInt32 nextMatchPrice = curAndLenCharPrice + _isMatch[(state2.Index << Base.kNumPosStatesBitsMax) + posStateNext].GetPrice1();
942 UInt32 nextRepMatchPrice = nextMatchPrice + _isRep[state2.Index].GetPrice1();
943
944 // for(; lenTest2 >= 2; lenTest2--)
945 {
946 UInt32 offset = lenTest + 1 + lenTest2;
947 while(lenEnd < cur + offset)
948 _optimum[++lenEnd].Price = kIfinityPrice;
949 UInt32 curAndLenPrice = nextRepMatchPrice + GetRepPrice(0, lenTest2, state2, posStateNext);
950 Optimal optimum = _optimum[cur + offset];
951 if (curAndLenPrice < optimum.Price)
952 {
953 optimum.Price = curAndLenPrice;
954 optimum.PosPrev = cur + lenTest + 1;
955 optimum.BackPrev = 0;
956 optimum.Prev1IsChar = true;
957 optimum.Prev2 = true;
958 optimum.PosPrev2 = cur;
959 optimum.BackPrev2 = repIndex;
960 }
961 }
962 }
963 }
964 }
965
966 // for(UInt32 lenTest = 2; lenTest <= newLen; lenTest++)
967 if (newLen > numAvailableBytes)
968 newLen = numAvailableBytes;
969 if (newLen >= 2)
970 {
971 if (newLen == 2 && _matchDistances[2] >= 0x80)
972 continue;
973 normalMatchPrice = matchPrice +
974 _isRep[state.Index].GetPrice0();
975 while (lenEnd < cur + newLen)
976 _optimum[++lenEnd].Price = kIfinityPrice;
977
978 for (UInt32 lenTest = newLen; lenTest >= 2; lenTest--)
979 {
980 UInt32 curBack = _matchDistances[lenTest];
981 UInt32 curAndLenPrice = normalMatchPrice + GetPosLenPrice(curBack, lenTest, posState);
982 Optimal optimum = _optimum[cur + lenTest];
983 if (curAndLenPrice < optimum.Price)
984 {
985 optimum.Price = curAndLenPrice;
986 optimum.PosPrev = cur;
987 optimum.BackPrev = curBack + Base.kNumRepDistances;
988 optimum.Prev1IsChar = false;
989 }
990
991 if (_maxMode && (lenTest == newLen || curBack != _matchDistances[lenTest + 1]))
992 {
993 UInt32 backOffset = curBack + 1;
994 UInt32 lenTest2 = lenTest + 1;
995 UInt32 limit = Math.Min(numAvailableBytesFull, lenTest2 + _numFastBytes);
996 for (; lenTest2 < limit; lenTest2++)
997 if (_matchFinder.GetIndexByte((Int32)lenTest2 - 1) != _matchFinder.GetIndexByte((Int32)lenTest2 - (Int32)backOffset - 1))
998 break;
999 lenTest2 -= lenTest + 1;
1000 if (lenTest2 >= 2)
1001 {
1002 Base.State state2 = state;
1003 state2.UpdateMatch();
1004 UInt32 posStateNext = (position + lenTest) & _posStateMask;
1005 UInt32 curAndLenCharPrice = curAndLenPrice +
1006 _isMatch[(state2.Index << Base.kNumPosStatesBitsMax) + posStateNext].GetPrice0() +
1007 _literalEncoder.GetSubCoder(position + lenTest,
1008 // data[(size_t)lenTest - 1],
1009 _matchFinder.GetIndexByte((Int32)lenTest - 1 - 1)).
1010 GetPrice(true,
1011 // data[(size_t)lenTest - backOffset], data[lenTest]
1012 _matchFinder.GetIndexByte((Int32)lenTest - (Int32)backOffset - 1),
1013 _matchFinder.GetIndexByte((Int32)lenTest - 1)
1014 );
1015 state2.UpdateChar();
1016 posStateNext = (position + lenTest + 1) & _posStateMask;
1017 UInt32 nextMatchPrice = curAndLenCharPrice + _isMatch[(state2.Index << Base.kNumPosStatesBitsMax) + posStateNext].GetPrice1();
1018 UInt32 nextRepMatchPrice = nextMatchPrice + _isRep[state2.Index].GetPrice1();
1019
1020 // for(; lenTest2 >= 2; lenTest2--)
1021 {
1022 UInt32 offset = lenTest + 1 + lenTest2;
1023 while (lenEnd < cur + offset)
1024 _optimum[++lenEnd].Price = kIfinityPrice;
1025 curAndLenPrice = nextRepMatchPrice + GetRepPrice(
1026 0, lenTest2, state2, posStateNext);
1027 optimum = _optimum[cur + offset];
1028 if (curAndLenPrice < optimum.Price)
1029 {
1030 optimum.Price = curAndLenPrice;
1031 optimum.PosPrev = cur + lenTest + 1;
1032 optimum.BackPrev = 0;
1033 optimum.Prev1IsChar = true;
1034 optimum.Prev2 = true;
1035 optimum.PosPrev2 = cur;
1036 optimum.BackPrev2 = curBack + Base.kNumRepDistances;
1037 }
1038 }
1039 }
1040 }
1041 }
1042 }
1043 }
1044 }
1045
1046 bool ChangePair(UInt32 smallDist, UInt32 bigDist)
1047 {
1048 const int kDif = 7;
1049 return (smallDist < ((UInt32)(1) << (32 - kDif)) && bigDist >= (smallDist << kDif));
1050 }
1051
1052 UInt32 GetOptimumFast(UInt32 position, out UInt32 backRes)
1053 {
1054 UInt32 lenMain;
1055 if (!_longestMatchWasFound)
1056 {
1057 ReadMatchDistances(out lenMain);
1058 }
1059 else
1060 {
1061 lenMain = _longestMatchLength;
1062 _longestMatchWasFound = false;
1063 }
1064 UInt32 repMaxIndex = 0;
1065 for (UInt32 i = 0; i < Base.kNumRepDistances; i++)
1066 {
1067 repLens[i] = _matchFinder.GetMatchLen(0 - 1, _repDistances[i], Base.kMatchMaxLen);
1068 if (i == 0 || repLens[i] > repLens[repMaxIndex])
1069 repMaxIndex = i;
1070 }
1071 if (repLens[repMaxIndex] >= _numFastBytes)
1072 {
1073 backRes = repMaxIndex;
1074 UInt32 lenRes = repLens[repMaxIndex];
1075 MovePos(lenRes - 1);
1076 return lenRes;
1077 }
1078 if (lenMain >= _numFastBytes)
1079 {
1080 backRes = _matchDistances[_numFastBytes] + Base.kNumRepDistances;
1081 MovePos(lenMain - 1);
1082 return lenMain;
1083 }
1084 while (lenMain > 2)
1085 {
1086 if (!ChangePair(_matchDistances[lenMain - 1], _matchDistances[lenMain]))
1087 break;
1088 lenMain--;
1089 }
1090 if (lenMain == 2 && _matchDistances[2] >= 0x80)
1091 lenMain = 1;
1092
1093 UInt32 backMain = _matchDistances[lenMain];
1094 if (repLens[repMaxIndex] >= 2)
1095 {
1096 if (repLens[repMaxIndex] + 1 >= lenMain ||
1097 repLens[repMaxIndex] + 2 >= lenMain && (backMain > (1 << 12)))
1098 {
1099 backRes = repMaxIndex;
1100 UInt32 lenRes = repLens[repMaxIndex];
1101 MovePos(lenRes - 1);
1102 return lenRes;
1103 }
1104 }
1105
1106 if (lenMain >= 2)
1107 {
1108 ReadMatchDistances(out _longestMatchLength);
1109 if (_longestMatchLength >= 2 &&
1110 (
1111 (_longestMatchLength >= lenMain &&
1112 _matchDistances[lenMain] < backMain) ||
1113 _longestMatchLength == lenMain + 1 &&
1114 !ChangePair(backMain, _matchDistances[_longestMatchLength]) ||
1115 _longestMatchLength > lenMain + 1 ||
1116 _longestMatchLength + 1 >= lenMain && lenMain >= 3 &&
1117 ChangePair(_matchDistances[lenMain - 1], backMain)
1118 )
1119 )
1120 {
1121 _longestMatchWasFound = true;
1122 backRes = 0xFFFFFFFF;
1123 return 1;
1124 }
1125 for (UInt32 i = 0; i < Base.kNumRepDistances; i++)
1126 {
1127 UInt32 repLen = _matchFinder.GetMatchLen(0 - 1, _repDistances[i], Base.kMatchMaxLen);
1128 if (repLen >= 2 && repLen + 1 >= lenMain)
1129 {
1130 _longestMatchWasFound = true;
1131 backRes = 0xFFFFFFFF;
1132 return 1;
1133 }
1134 }
1135 backRes = backMain + Base.kNumRepDistances;
1136 MovePos(lenMain - 2);
1137 return lenMain;
1138 }
1139 backRes = 0xFFFFFFFF;
1140 return 1;
1141 }
1142
1143 void InitMatchFinder(LZ.IMatchFinder matchFinder)
1144 {
1145 _matchFinder = matchFinder;
1146 }
1147
1148 void WriteEndMarker(UInt32 posState)
1149 {
1150 if (!_writeEndMark)
1151 return;
1152
1153 _isMatch[(_state.Index << Base.kNumPosStatesBitsMax) + posState].Encode(_rangeEncoder, 1);
1154 _isRep[_state.Index].Encode(_rangeEncoder, 0);
1155 _state.UpdateMatch();
1156 UInt32 len = Base.kMatchMinLen; // kMatchMaxLen;
1157 _lenEncoder.Encode(_rangeEncoder, len - Base.kMatchMinLen, posState);
1158 UInt32 posSlot = (1 << Base.kNumPosSlotBits) - 1;
1159 UInt32 lenToPosState = Base.GetLenToPosState(len);
1160 _posSlotEncoder[lenToPosState].Encode(_rangeEncoder, posSlot);
1161 int footerBits = 30;
1162 UInt32 posReduced = (((UInt32)1) << footerBits) - 1;
1163 _rangeEncoder.EncodeDirectBits(posReduced >> Base.kNumAlignBits, footerBits - Base.kNumAlignBits);
1164 _posAlignEncoder.ReverseEncode(_rangeEncoder, posReduced & Base.kAlignMask);
1165 }
1166
1167 void Flush(UInt32 nowPos)
1168 {
1169 ReleaseMFStream();
1170 WriteEndMarker(nowPos & _posStateMask);
1171 _rangeEncoder.FlushData();
1172 _rangeEncoder.FlushStream();
1173 }
1174
1175 public void CodeOneBlock(out Int64 inSize, out Int64 outSize, out bool finished)
1176 {
1177 inSize = 0;
1178 outSize = 0;
1179 finished = true;
1180
1181 if (_inStream != null)
1182 {
1183 _matchFinder.Init(_inStream);
1184 _needReleaseMFStream = true;
1185 _inStream = null;
1186 }
1187
1188 if (_finished)
1189 return;
1190 _finished = true;
1191
1192
1193 Int64 progressPosValuePrev = nowPos64;
1194 if (nowPos64 == 0)
1195 {
1196 if (_matchFinder.GetNumAvailableBytes() == 0)
1197 {
1198 Flush((UInt32)nowPos64);
1199 return;
1200 }
1201 UInt32 len; // it's not used
1202 ReadMatchDistances(out len);
1203 UInt32 posState = (UInt32)(nowPos64) & _posStateMask;
1204 _isMatch[(_state.Index << Base.kNumPosStatesBitsMax) + posState].Encode(_rangeEncoder, 0);
1205 _state.UpdateChar();
1206 Byte curByte = _matchFinder.GetIndexByte((Int32)(0 - _additionalOffset));
1207 _literalEncoder.GetSubCoder((UInt32)(nowPos64), _previousByte).Encode(_rangeEncoder, curByte);
1208 _previousByte = curByte;
1209 _additionalOffset--;
1210 nowPos64++;
1211 }
1212 if (_matchFinder.GetNumAvailableBytes() == 0)
1213 {
1214 Flush((UInt32)nowPos64);
1215 return;
1216 }
1217 while (true)
1218 {
1219 UInt32 pos;
1220 UInt32 posState = ((UInt32)nowPos64) & _posStateMask;
1221
1222 UInt32 len;
1223 if (_fastMode)
1224 len = GetOptimumFast((UInt32)nowPos64, out pos);
1225 else
1226 len = GetOptimum((UInt32)nowPos64, out pos);
1227
1228 UInt32 complexState = (_state.Index << Base.kNumPosStatesBitsMax) + posState;
1229 if (len == 1 && pos == 0xFFFFFFFF)
1230 {
1231 _isMatch[complexState].Encode(_rangeEncoder, 0);
1232 Byte curByte = _matchFinder.GetIndexByte((Int32)(0 - _additionalOffset));
1233 LiteralEncoder.Encoder2 subCoder = _literalEncoder.GetSubCoder((UInt32)nowPos64, _previousByte);
1234 if (!_state.IsCharState())
1235 {
1236 Byte matchByte = _matchFinder.GetIndexByte((Int32)(0 - _repDistances[0] - 1 - _additionalOffset));
1237 subCoder.EncodeMatched(_rangeEncoder, matchByte, curByte);
1238 }
1239 else
1240 subCoder.Encode(_rangeEncoder, curByte);
1241 _previousByte = curByte;
1242 _state.UpdateChar();
1243 }
1244 else
1245 {
1246 _isMatch[complexState].Encode(_rangeEncoder, 1);
1247 if (pos < Base.kNumRepDistances)
1248 {
1249 _isRep[_state.Index].Encode(_rangeEncoder, 1);
1250 if (pos == 0)
1251 {
1252 _isRepG0[_state.Index].Encode(_rangeEncoder, 0);
1253 if (len == 1)
1254 _isRep0Long[complexState].Encode(_rangeEncoder, 0);
1255 else
1256 _isRep0Long[complexState].Encode(_rangeEncoder, 1);
1257 }
1258 else
1259 {
1260 _isRepG0[_state.Index].Encode(_rangeEncoder, 1);
1261 if (pos == 1)
1262 _isRepG1[_state.Index].Encode(_rangeEncoder, 0);
1263 else
1264 {
1265 _isRepG1[_state.Index].Encode(_rangeEncoder, 1);
1266 _isRepG2[_state.Index].Encode(_rangeEncoder, pos - 2);
1267 }
1268 }
1269 if (len == 1)
1270 _state.UpdateShortRep();
1271 else
1272 {
1273 _repMatchLenEncoder.Encode(_rangeEncoder, len - Base.kMatchMinLen, posState);
1274 _state.UpdateRep();
1275 }
1276
1277
1278 UInt32 distance = _repDistances[pos];
1279 if (pos != 0)
1280 {
1281 for (UInt32 i = pos; i >= 1; i--)
1282 _repDistances[i] = _repDistances[i - 1];
1283 _repDistances[0] = distance;
1284 }
1285 }
1286 else
1287 {
1288 _isRep[_state.Index].Encode(_rangeEncoder, 0);
1289 _state.UpdateMatch();
1290 _lenEncoder.Encode(_rangeEncoder, len - Base.kMatchMinLen, posState);
1291 pos -= Base.kNumRepDistances;
1292 UInt32 posSlot = GetPosSlot(pos);
1293 UInt32 lenToPosState = Base.GetLenToPosState(len);
1294 _posSlotEncoder[lenToPosState].Encode(_rangeEncoder, posSlot);
1295
1296 if (posSlot >= Base.kStartPosModelIndex)
1297 {
1298 int footerBits = (int)((posSlot >> 1) - 1);
1299 UInt32 baseVal = ((2 | (posSlot & 1)) << footerBits);
1300 UInt32 posReduced = pos - baseVal;
1301
1302 if (posSlot < Base.kEndPosModelIndex)
1303 RangeCoder.BitTreeEncoder.ReverseEncode(_posEncoders,
1304 baseVal - posSlot - 1, _rangeEncoder, footerBits, posReduced);
1305 else
1306 {
1307 _rangeEncoder.EncodeDirectBits(posReduced >> Base.kNumAlignBits, footerBits - Base.kNumAlignBits);
1308 _posAlignEncoder.ReverseEncode(_rangeEncoder, posReduced & Base.kAlignMask);
1309 if (!_fastMode)
1310 if (--_alignPriceCount == 0)
1311 FillAlignPrices();
1312 }
1313 }
1314 UInt32 distance = pos;
1315 for (UInt32 i = Base.kNumRepDistances - 1; i >= 1; i--)
1316 _repDistances[i] = _repDistances[i - 1];
1317 _repDistances[0] = distance;
1318 }
1319 _previousByte = _matchFinder.GetIndexByte((Int32)(len - 1 - _additionalOffset));
1320 }
1321 _additionalOffset -= len;
1322 nowPos64 += len;
1323 if (!_fastMode)
1324 if (nowPos64 - lastPosSlotFillingPos >= (1 << 9))
1325 {
1326 FillPosSlotPrices();
1327 FillDistancesPrices();
1328 lastPosSlotFillingPos = nowPos64;
1329 }
1330 if (_additionalOffset == 0)
1331 {
1332 inSize = nowPos64;
1333 outSize = _rangeEncoder.GetProcessedSizeAdd();
1334 if (_matchFinder.GetNumAvailableBytes() == 0)
1335 {
1336 Flush((UInt32)nowPos64);
1337 return;
1338 }
1339
1340 if (nowPos64 - progressPosValuePrev >= (1 << 12))
1341 {
1342 _finished = false;
1343 finished = false;
1344 return;
1345 }
1346 }
1347 }
1348 }
1349
1350 void ReleaseMFStream()
1351 {
1352 if (_matchFinder != null && _needReleaseMFStream)
1353 {
1354 _matchFinder.ReleaseStream();
1355 _needReleaseMFStream = false;
1356 }
1357 }
1358
1359 void SetOutStream(System.IO.Stream outStream) { _rangeEncoder.SetStream(outStream); }
1360 void ReleaseOutStream() { _rangeEncoder.ReleaseStream(); }
1361
1362 void ReleaseStreams()
1363 {
1364 ReleaseMFStream();
1365 ReleaseOutStream();
1366 }
1367
1368 void SetStreams(System.IO.Stream inStream, System.IO.Stream outStream,
1369 Int64 inSize, Int64 outSize)
1370 {
1371 _inStream = inStream;
1372 _finished = false;
1373 Create();
1374 SetOutStream(outStream);
1375 Init();
1376
1377 // CCoderReleaser releaser(this);
1378
1379 /*
1380 if (_matchFinder->GetNumAvailableBytes() == 0)
1381 return Flush();
1382 */
1383
1384 if (!_fastMode)
1385 {
1386 FillPosSlotPrices();
1387 FillDistancesPrices();
1388 FillAlignPrices();
1389 }
1390
1391 _lenEncoder.SetTableSize(_numFastBytes + 1 - Base.kMatchMinLen);
1392 _lenEncoder.UpdateTables((UInt32)1 << _posStateBits);
1393 _repMatchLenEncoder.SetTableSize(_numFastBytes + 1 - Base.kMatchMinLen);
1394 _repMatchLenEncoder.UpdateTables((UInt32)1 << _posStateBits);
1395
1396 lastPosSlotFillingPos = 0;
1397 nowPos64 = 0;
1398 }
1399
1400 public void Code(System.IO.Stream inStream, System.IO.Stream outStream,
1401 Int64 inSize, Int64 outSize, ICodeProgress progress)
1402 {
1403 _needReleaseMFStream = false;
1404 try
1405 {
1406 SetStreams(inStream, outStream, inSize, outSize);
1407 while (true)
1408 {
1409 Int64 processedInSize;
1410 Int64 processedOutSize;
1411 bool finished;
1412 CodeOneBlock(out processedInSize, out processedOutSize, out finished);
1413 if (finished)
1414 return;
1415 if (progress != null)
1416 {
1417 progress.SetProgress(processedInSize, processedOutSize);
1418 }
1419 }
1420 }
1421 finally
1422 {
1423 ReleaseStreams();
1424 }
1425 }
1426
1427 public void SetCoderProperties(CoderPropID[] propIDs, object[] properties)
1428 {
1429 for (UInt32 i = 0; i < properties.Length; i++)
1430 {
1431 object prop = properties[i];
1432 switch (propIDs[i])
1433 {
1434 case CoderPropID.NumFastBytes:
1435 {
1436 if (!(prop is Int32))
1437 throw new InvalidParamException();
1438 Int32 numFastBytes = (Int32)prop;
1439 if (numFastBytes < 5 || numFastBytes > Base.kMatchMaxLen)
1440 throw new InvalidParamException();
1441 _numFastBytes = (UInt32)numFastBytes;
1442 break;
1443 }
1444 case CoderPropID.Algorithm:
1445 {
1446 if (!(prop is Int32))
1447 throw new InvalidParamException();
1448 Int32 maximize = (Int32)prop;
1449 _fastMode = (maximize == 0);
1450 _maxMode = (maximize >= 2);
1451 break;
1452 }
1453 case CoderPropID.MatchFinder:
1454 {
1455 if (!(prop is String))
1456 throw new InvalidParamException();
1457 EMatchFinderType matchFinderIndexPrev = _matchFinderType;
1458 int m = FindMatchFinder(((string)prop).ToUpper());
1459 if (m < 0)
1460 throw new InvalidParamException();
1461 _matchFinderType = (EMatchFinderType)m;
1462 if (_matchFinder != null && matchFinderIndexPrev != _matchFinderType)
1463 {
1464 _dictionarySizePrev = 0xFFFFFFFF;
1465 _matchFinder = null;
1466 }
1467 break;
1468 }
1469 case CoderPropID.DictionarySize:
1470 {
1471 const int kDicLogSizeMaxCompress = 28;
1472 if (!(prop is Int32))
1473 throw new InvalidParamException(); ;
1474 Int32 dictionarySize = (Int32)prop;
1475 if (dictionarySize < (UInt32)(1 << Base.kDicLogSizeMin) ||
1476 dictionarySize > (UInt32)(1 << kDicLogSizeMaxCompress))
1477 throw new InvalidParamException();
1478 _dictionarySize = (UInt32)dictionarySize;
1479 int dicLogSize;
1480 for (dicLogSize = 0; dicLogSize < (UInt32)kDicLogSizeMaxCompress; dicLogSize++)
1481 if (dictionarySize <= ((UInt32)(1) << dicLogSize))
1482 break;
1483 _distTableSize = (UInt32)dicLogSize * 2;
1484 break;
1485 }
1486 case CoderPropID.PosStateBits:
1487 {
1488 if (!(prop is Int32))
1489 throw new InvalidParamException();
1490 Int32 v = (Int32)prop;
1491 if (v < 0 || v > (UInt32)Base.kNumPosStatesBitsEncodingMax)
1492 throw new InvalidParamException();
1493 _posStateBits = (int)v;
1494 _posStateMask = (((UInt32)1) << (int)_posStateBits) - 1;
1495 break;
1496 }
1497 case CoderPropID.LitPosBits:
1498 {
1499 if (!(prop is Int32))
1500 throw new InvalidParamException();
1501 Int32 v = (Int32)prop;
1502 if (v < 0 || v > (UInt32)Base.kNumLitPosStatesBitsEncodingMax)
1503 throw new InvalidParamException();
1504 _numLiteralPosStateBits = (int)v;
1505 break;
1506 }
1507 case CoderPropID.LitContextBits:
1508 {
1509 if (!(prop is Int32))
1510 throw new InvalidParamException();
1511 Int32 v = (Int32)prop;
1512 if (v < 0 || v > (UInt32)Base.kNumLitContextBitsMax)
1513 throw new InvalidParamException(); ;
1514 _numLiteralContextBits = (int)v;
1515 break;
1516 }
1517 case CoderPropID.EndMarker:
1518 {
1519 if (!(prop is Boolean))
1520 throw new InvalidParamException();
1521 SetWriteEndMarkerMode((Boolean)prop);
1522 break;
1523 }
1524 default:
1525 throw new InvalidParamException();
1526 }
1527 }
1528 }
1529
1530 const int kPropSize = 5;
1531 Byte[] properties = new Byte[kPropSize];
1532
1533 public void WriteCoderProperties(System.IO.Stream outStream)
1534 {
1535 properties[0] = (Byte)((_posStateBits * 5 + _numLiteralPosStateBits) * 9 + _numLiteralContextBits);
1536 for (int i = 0; i < 4; i++)
1537 properties[1 + i] = (Byte)(_dictionarySize >> (8 * i));
1538 outStream.Write(properties, 0, kPropSize);
1539 }
1540
1541 void FillPosSlotPrices()
1542 {
1543 for (UInt32 lenToPosState = 0; lenToPosState < Base.kNumLenToPosStates; lenToPosState++)
1544 {
1545 UInt32 posSlot;
1546 for (posSlot = 0; posSlot < Base.kEndPosModelIndex && posSlot < _distTableSize; posSlot++)
1547 _posSlotPrices[(posSlot << Base.kNumLenToPosStatesBits) + lenToPosState] = _posSlotEncoder[lenToPosState].GetPrice(posSlot);
1548 for (; posSlot < _distTableSize; posSlot++)
1549 _posSlotPrices[(posSlot << Base.kNumLenToPosStatesBits) + lenToPosState] = _posSlotEncoder[lenToPosState].GetPrice(posSlot) +
1550 ((((posSlot >> 1) - 1) - Base.kNumAlignBits) << RangeCoder.BitEncoder.kNumBitPriceShiftBits);
1551 }
1552 }
1553
1554 void FillDistancesPrices()
1555 {
1556 for (UInt32 lenToPosState = 0; lenToPosState < Base.kNumLenToPosStates; lenToPosState++)
1557 {
1558 UInt32 i;
1559 for (i = 0; i < Base.kStartPosModelIndex; i++)
1560 _distancesPrices[(i << Base.kNumLenToPosStatesBits) + lenToPosState] = _posSlotPrices[(i << Base.kNumLenToPosStatesBits) + lenToPosState];
1561 for (; i < Base.kNumFullDistances; i++)
1562 {
1563 UInt32 posSlot = GetPosSlot(i);
1564 int footerBits = (int)((posSlot >> 1) - 1);
1565 UInt32 baseVal = ((2 | (posSlot & 1)) << footerBits);
1566
1567 _distancesPrices[(i << Base.kNumLenToPosStatesBits) + lenToPosState] = _posSlotPrices[(posSlot << Base.kNumLenToPosStatesBits) + lenToPosState] +
1568 RangeCoder.BitTreeEncoder.ReverseGetPrice(_posEncoders,
1569 baseVal - posSlot - 1, footerBits, i - baseVal);
1570 }
1571 }
1572 }
1573
1574 void FillAlignPrices()
1575 {
1576 for (UInt32 i = 0; i < Base.kAlignTableSize; i++)
1577 _alignPrices[i] = _posAlignEncoder.ReverseGetPrice(i);
1578 _alignPriceCount = Base.kAlignTableSize;
1579 }
1580 }
1581 }
Tomato firmware and modifications.