|
rlm@1
|
1 // ShrinkDecoder.cpp
|
|
rlm@1
|
2
|
|
rlm@1
|
3 #include "StdAfx.h"
|
|
rlm@1
|
4
|
|
rlm@1
|
5 extern "C"
|
|
rlm@1
|
6 {
|
|
rlm@1
|
7 #include "../../../C/Alloc.h"
|
|
rlm@1
|
8 }
|
|
rlm@1
|
9
|
|
rlm@1
|
10 #include "../Common/InBuffer.h"
|
|
rlm@1
|
11 #include "../Common/OutBuffer.h"
|
|
rlm@1
|
12
|
|
rlm@1
|
13 #include "BitlDecoder.h"
|
|
rlm@1
|
14 #include "ShrinkDecoder.h"
|
|
rlm@1
|
15
|
|
rlm@1
|
16 namespace NCompress {
|
|
rlm@1
|
17 namespace NShrink {
|
|
rlm@1
|
18
|
|
rlm@1
|
19 static const UInt32 kBufferSize = (1 << 20);
|
|
rlm@1
|
20 static const int kNumMinBits = 9;
|
|
rlm@1
|
21
|
|
rlm@1
|
22 HRESULT CDecoder::CodeReal(ISequentialInStream *inStream, ISequentialOutStream *outStream,
|
|
rlm@1
|
23 const UInt64 * /* inSize */, const UInt64 * /* outSize */, ICompressProgressInfo *progress)
|
|
rlm@1
|
24 {
|
|
rlm@1
|
25 NBitl::CBaseDecoder<CInBuffer> inBuffer;
|
|
rlm@1
|
26 COutBuffer outBuffer;
|
|
rlm@1
|
27
|
|
rlm@1
|
28 if (!inBuffer.Create(kBufferSize))
|
|
rlm@1
|
29 return E_OUTOFMEMORY;
|
|
rlm@1
|
30 inBuffer.SetStream(inStream);
|
|
rlm@1
|
31 inBuffer.Init();
|
|
rlm@1
|
32
|
|
rlm@1
|
33 if (!outBuffer.Create(kBufferSize))
|
|
rlm@1
|
34 return E_OUTOFMEMORY;
|
|
rlm@1
|
35 outBuffer.SetStream(outStream);
|
|
rlm@1
|
36 outBuffer.Init();
|
|
rlm@1
|
37
|
|
rlm@1
|
38 UInt64 prevPos = 0;
|
|
rlm@1
|
39 int numBits = kNumMinBits;
|
|
rlm@1
|
40 UInt32 head = 257;
|
|
rlm@1
|
41 bool needPrev = false;
|
|
rlm@1
|
42 UInt32 lastSymbol = 0;
|
|
rlm@1
|
43
|
|
rlm@1
|
44 int i;
|
|
rlm@1
|
45 for (i = 0; i < kNumItems; i++)
|
|
rlm@1
|
46 _parents[i] = 0;
|
|
rlm@1
|
47 for (i = 0; i < kNumItems; i++)
|
|
rlm@1
|
48 _suffixes[i] = 0;
|
|
rlm@1
|
49 for (i = 0; i < 257; i++)
|
|
rlm@1
|
50 _isFree[i] = false;
|
|
rlm@1
|
51 for (; i < kNumItems; i++)
|
|
rlm@1
|
52 _isFree[i] = true;
|
|
rlm@1
|
53
|
|
rlm@1
|
54 for (;;)
|
|
rlm@1
|
55 {
|
|
rlm@1
|
56 UInt32 symbol = inBuffer.ReadBits(numBits);
|
|
rlm@1
|
57 if (inBuffer.ExtraBitsWereRead())
|
|
rlm@1
|
58 break;
|
|
rlm@1
|
59 if (_isFree[symbol])
|
|
rlm@1
|
60 return S_FALSE;
|
|
rlm@1
|
61 if (symbol == 256)
|
|
rlm@1
|
62 {
|
|
rlm@1
|
63 UInt32 symbol = inBuffer.ReadBits(numBits);
|
|
rlm@1
|
64 if (symbol == 1)
|
|
rlm@1
|
65 {
|
|
rlm@1
|
66 if (numBits < kNumMaxBits)
|
|
rlm@1
|
67 numBits++;
|
|
rlm@1
|
68 }
|
|
rlm@1
|
69 else if (symbol == 2)
|
|
rlm@1
|
70 {
|
|
rlm@1
|
71 if (needPrev)
|
|
rlm@1
|
72 _isFree[head - 1] = true;
|
|
rlm@1
|
73 for (i = 257; i < kNumItems; i++)
|
|
rlm@1
|
74 _isParent[i] = false;
|
|
rlm@1
|
75 for (i = 257; i < kNumItems; i++)
|
|
rlm@1
|
76 if (!_isFree[i])
|
|
rlm@1
|
77 _isParent[_parents[i]] = true;
|
|
rlm@1
|
78 for (i = 257; i < kNumItems; i++)
|
|
rlm@1
|
79 if (!_isParent[i])
|
|
rlm@1
|
80 _isFree[i] = true;
|
|
rlm@1
|
81 head = 257;
|
|
rlm@1
|
82 while (head < kNumItems && !_isFree[head])
|
|
rlm@1
|
83 head++;
|
|
rlm@1
|
84 if (head < kNumItems)
|
|
rlm@1
|
85 {
|
|
rlm@1
|
86 needPrev = true;
|
|
rlm@1
|
87 _isFree[head] = false;
|
|
rlm@1
|
88 _parents[head] = (UInt16)lastSymbol;
|
|
rlm@1
|
89 head++;
|
|
rlm@1
|
90 }
|
|
rlm@1
|
91 }
|
|
rlm@1
|
92 else
|
|
rlm@1
|
93 return S_FALSE;
|
|
rlm@1
|
94 continue;
|
|
rlm@1
|
95 }
|
|
rlm@1
|
96 UInt32 cur = symbol;
|
|
rlm@1
|
97 i = 0;
|
|
rlm@1
|
98 int corectionIndex = -1;
|
|
rlm@1
|
99 while (cur >= 256)
|
|
rlm@1
|
100 {
|
|
rlm@1
|
101 if (cur == head - 1)
|
|
rlm@1
|
102 corectionIndex = i;
|
|
rlm@1
|
103 _stack[i++] = _suffixes[cur];
|
|
rlm@1
|
104 cur = _parents[cur];
|
|
rlm@1
|
105 }
|
|
rlm@1
|
106 _stack[i++] = (Byte)cur;
|
|
rlm@1
|
107 if (needPrev)
|
|
rlm@1
|
108 {
|
|
rlm@1
|
109 _suffixes[head - 1] = (Byte)cur;
|
|
rlm@1
|
110 if (corectionIndex >= 0)
|
|
rlm@1
|
111 _stack[corectionIndex] = (Byte)cur;
|
|
rlm@1
|
112 }
|
|
rlm@1
|
113 while (i > 0)
|
|
rlm@1
|
114 outBuffer.WriteByte((_stack[--i]));
|
|
rlm@1
|
115 while (head < kNumItems && !_isFree[head])
|
|
rlm@1
|
116 head++;
|
|
rlm@1
|
117 if (head < kNumItems)
|
|
rlm@1
|
118 {
|
|
rlm@1
|
119 needPrev = true;
|
|
rlm@1
|
120 _isFree[head] = false;
|
|
rlm@1
|
121 _parents[head] = (UInt16)symbol;
|
|
rlm@1
|
122 head++;
|
|
rlm@1
|
123 }
|
|
rlm@1
|
124 else
|
|
rlm@1
|
125 needPrev = false;
|
|
rlm@1
|
126 lastSymbol = symbol;
|
|
rlm@1
|
127
|
|
rlm@1
|
128 UInt64 nowPos = outBuffer.GetProcessedSize();
|
|
rlm@1
|
129 if (progress != NULL && nowPos - prevPos > (1 << 18))
|
|
rlm@1
|
130 {
|
|
rlm@1
|
131 prevPos = nowPos;
|
|
rlm@1
|
132 UInt64 packSize = inBuffer.GetProcessedSize();
|
|
rlm@1
|
133 RINOK(progress->SetRatioInfo(&packSize, &nowPos));
|
|
rlm@1
|
134 }
|
|
rlm@1
|
135 }
|
|
rlm@1
|
136 return outBuffer.Flush();
|
|
rlm@1
|
137 }
|
|
rlm@1
|
138
|
|
rlm@1
|
139 STDMETHODIMP CDecoder ::Code(ISequentialInStream *inStream, ISequentialOutStream *outStream,
|
|
rlm@1
|
140 const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress)
|
|
rlm@1
|
141 {
|
|
rlm@1
|
142 try { return CodeReal(inStream, outStream, inSize, outSize, progress); }
|
|
rlm@1
|
143 catch(const CInBufferException &e) { return e.ErrorCode; }
|
|
rlm@1
|
144 catch(const COutBufferException &e) { return e.ErrorCode; }
|
|
rlm@1
|
145 catch(...) { return S_FALSE; }
|
|
rlm@1
|
146 }
|
|
rlm@1
|
147
|
|
rlm@1
|
148 }}
|
