|
1 // Copyright (c) 1998-2009 Nokia Corporation and/or its subsidiary(-ies). |
|
2 // All rights reserved. |
|
3 // This component and the accompanying materials are made available |
|
4 // under the terms of "Eclipse Public License v1.0" |
|
5 // which accompanies this distribution, and is available |
|
6 // at the URL "http://www.eclipse.org/legal/epl-v10.html". |
|
7 // |
|
8 // Initial Contributors: |
|
9 // Nokia Corporation - initial contribution. |
|
10 // |
|
11 // Contributors: |
|
12 // |
|
13 // Description: |
|
14 // e32tools\petran\Szip\deflate.cpp |
|
15 // |
|
16 // |
|
17 |
|
18 #include "deflate.h" |
|
19 #include "h_utl.h" |
|
20 #include "panic.h" |
|
21 |
|
22 class HDeflateHash |
|
23 { |
|
24 public: |
|
25 inline static HDeflateHash* NewLC(TInt aLinks); |
|
26 // |
|
27 inline TInt First(const TUint8* aPtr,TInt aPos); |
|
28 inline TInt Next(TInt aPos,TInt aOffset) const; |
|
29 private: |
|
30 inline HDeflateHash(); |
|
31 inline static TInt Hash(const TUint8* aPtr); |
|
32 private: |
|
33 typedef TUint16 TOffset; |
|
34 private: |
|
35 TInt iHash[256]; |
|
36 TOffset iOffset[1]; // or more |
|
37 }; |
|
38 |
|
39 class MDeflater |
|
40 { |
|
41 public: |
|
42 void DeflateL(const TUint8* aBase,TInt aLength); |
|
43 inline virtual ~MDeflater() { }; |
|
44 private: |
|
45 const TUint8* DoDeflateL(const TUint8* aBase,const TUint8* aEnd,HDeflateHash& aHash); |
|
46 static TInt Match(const TUint8* aPtr,const TUint8* aEnd,TInt aPos,HDeflateHash& aHas); |
|
47 void SegmentL(TInt aLength,TInt aDistance); |
|
48 virtual void LitLenL(TInt aCode) =0; |
|
49 virtual void OffsetL(TInt aCode) =0; |
|
50 virtual void ExtraL(TInt aLen,TUint aBits) =0; |
|
51 }; |
|
52 |
|
53 class TDeflateStats : public MDeflater |
|
54 { |
|
55 public: |
|
56 inline TDeflateStats(TEncoding& aEncoding); |
|
57 inline virtual ~TDeflateStats() { } |
|
58 private: |
|
59 // from MDeflater |
|
60 void LitLenL(TInt aCode); |
|
61 void OffsetL(TInt aCode); |
|
62 void ExtraL(TInt aLen,TUint aBits); |
|
63 private: |
|
64 TEncoding& iEncoding; |
|
65 }; |
|
66 |
|
67 class TDeflater : public MDeflater |
|
68 { |
|
69 public: |
|
70 inline TDeflater(TBitOutput& aOutput,const TEncoding& aEncoding); |
|
71 inline virtual ~TDeflater() { }; |
|
72 private: |
|
73 // from MDeflater |
|
74 void LitLenL(TInt aCode); |
|
75 void OffsetL(TInt aCode); |
|
76 void ExtraL(TInt aLen,TUint aBits); |
|
77 private: |
|
78 TBitOutput& iOutput; |
|
79 const TEncoding& iEncoding; |
|
80 }; |
|
81 |
|
82 |
|
83 // Class HDeflateHash |
|
84 |
|
85 inline HDeflateHash::HDeflateHash() |
|
86 {TInt* p=iHash+256;do *--p=-KDeflateMaxDistance-1; while (p>iHash);} |
|
87 |
|
88 inline HDeflateHash* HDeflateHash::NewLC(TInt aLinks) |
|
89 { |
|
90 #if __GNUC__ >= 4 |
|
91 unsigned n = sizeof(TInt) * 256 + sizeof(TOffset) * Min(aLinks, KDeflateMaxDistance); |
|
92 |
|
93 while (n & 0x1f) |
|
94 { |
|
95 n++; |
|
96 } |
|
97 |
|
98 void* p = ::operator new(n); |
|
99 |
|
100 return new(p) HDeflateHash; |
|
101 #else |
|
102 return new(HMem::Alloc(0,_FOFF(HDeflateHash,iOffset[Min(aLinks,KDeflateMaxDistance)]))) HDeflateHash; |
|
103 #endif |
|
104 } |
|
105 |
|
106 inline TInt HDeflateHash::Hash(const TUint8* aPtr) |
|
107 { |
|
108 TUint x=aPtr[0]|(aPtr[1]<<8)|(aPtr[2]<<16); |
|
109 return (x*KDeflateHashMultiplier)>>KDeflateHashShift; |
|
110 } |
|
111 |
|
112 inline TInt HDeflateHash::First(const TUint8* aPtr,TInt aPos) |
|
113 { |
|
114 TInt h=Hash(aPtr); |
|
115 TInt offset=Min(aPos-iHash[h],KDeflateMaxDistance<<1); |
|
116 iHash[h]=aPos; |
|
117 iOffset[aPos&(KDeflateMaxDistance-1)]=TOffset(offset); |
|
118 return offset; |
|
119 } |
|
120 |
|
121 inline TInt HDeflateHash::Next(TInt aPos,TInt aOffset) const |
|
122 {return aOffset+iOffset[(aPos-aOffset)&(KDeflateMaxDistance-1)];} |
|
123 |
|
124 |
|
125 // Class TDeflater |
|
126 // |
|
127 // generic deflation algorithm, can do either statistics and the encoder |
|
128 |
|
129 TInt MDeflater::Match(const TUint8* aPtr,const TUint8* aEnd,TInt aPos,HDeflateHash& aHash) |
|
130 { |
|
131 TInt offset=aHash.First(aPtr,aPos); |
|
132 if (offset>KDeflateMaxDistance) |
|
133 return 0; |
|
134 TInt match=0; |
|
135 aEnd=Min(aEnd,aPtr+KDeflateMaxLength); |
|
136 TUint8 c=*aPtr; |
|
137 do |
|
138 { |
|
139 const TUint8* p=aPtr-offset; |
|
140 if (p[match>>16]==c) |
|
141 { // might be a better match |
|
142 const TUint8* m=aPtr; |
|
143 for (;;) |
|
144 { |
|
145 if (*p++!=*m++) |
|
146 break; |
|
147 if (m<aEnd) |
|
148 continue; |
|
149 return ((m-aPtr)<<16)|offset; |
|
150 } |
|
151 TInt l=m-aPtr-1; |
|
152 if (l>match>>16) |
|
153 { |
|
154 match=(l<<16)|offset; |
|
155 c=m[-1]; |
|
156 } |
|
157 } |
|
158 offset=aHash.Next(aPos,offset); |
|
159 } while (offset<=KDeflateMaxDistance); |
|
160 return match; |
|
161 } |
|
162 |
|
163 const TUint8* MDeflater::DoDeflateL(const TUint8* aBase,const TUint8* aEnd,HDeflateHash& aHash) |
|
164 // |
|
165 // Apply the deflation algorithm to the data [aBase,aEnd) |
|
166 // Return a pointer after the last byte that was deflated (which may not be aEnd) |
|
167 // |
|
168 { |
|
169 const TUint8* ptr=aBase; |
|
170 TInt prev=0; // the previous deflation match |
|
171 do |
|
172 { |
|
173 TInt match=Match(ptr,aEnd,ptr-aBase,aHash); |
|
174 // Extra deflation applies two optimisations which double the time taken |
|
175 // 1. If we have a match at p, then test for a better match at p+1 before using it |
|
176 // 2. When we have a match, add the hash links for all the data which will be skipped |
|
177 if (match>>16 < prev>>16) |
|
178 { // use the previous match--it was better |
|
179 TInt len=prev>>16; |
|
180 SegmentL(len,prev-(len<<16)); |
|
181 // fill in missing hash entries for better compression |
|
182 const TUint8* e=ptr+len-2; |
|
183 do |
|
184 { |
|
185 ++ptr; |
|
186 if (ptr + 2 < aEnd) |
|
187 aHash.First(ptr,ptr-aBase); |
|
188 } while (ptr<e); |
|
189 prev=0; |
|
190 } |
|
191 else if (match<=(KDeflateMinLength<<16)) |
|
192 LitLenL(*ptr); // no deflation match here |
|
193 else |
|
194 { // save this match and test the next position |
|
195 if (prev) // we had a match at ptr-1, but this is better |
|
196 LitLenL(ptr[-1]); |
|
197 prev=match; |
|
198 } |
|
199 ++ptr; |
|
200 } while (ptr+KDeflateMinLength-1<aEnd); |
|
201 if (prev) |
|
202 { // emit the stored match |
|
203 TInt len=prev>>16; |
|
204 SegmentL(len,prev-(len<<16)); |
|
205 ptr+=len-1; |
|
206 } |
|
207 return ptr; |
|
208 } |
|
209 |
|
210 void MDeflater::DeflateL(const TUint8* aBase,TInt aLength) |
|
211 // |
|
212 // The generic deflation algorithm |
|
213 // |
|
214 { |
|
215 const TUint8* end=aBase+aLength; |
|
216 if (aLength>KDeflateMinLength) |
|
217 { // deflation kicks in if there is enough data |
|
218 HDeflateHash* hash=HDeflateHash::NewLC(aLength); |
|
219 if(hash==NULL) |
|
220 Panic(EHuffmanOutOfMemory); |
|
221 |
|
222 aBase=DoDeflateL(aBase,end,*hash); |
|
223 delete hash; |
|
224 } |
|
225 while (aBase<end) // emit remaining bytes |
|
226 LitLenL(*aBase++); |
|
227 LitLenL(TEncoding::EEos); // eos marker |
|
228 } |
|
229 |
|
230 void MDeflater::SegmentL(TInt aLength,TInt aDistance) |
|
231 // |
|
232 // Turn a (length,offset) pair into the deflation codes+extra bits before calling |
|
233 // the specific LitLen(), Offset() and Extra() functions. |
|
234 // |
|
235 { |
|
236 aLength-=KDeflateMinLength; |
|
237 TInt extralen=0; |
|
238 TUint len=aLength; |
|
239 while (len>=8) |
|
240 { |
|
241 ++extralen; |
|
242 len>>=1; |
|
243 } |
|
244 LitLenL((extralen<<2)+len+TEncoding::ELiterals); |
|
245 if (extralen) |
|
246 ExtraL(extralen,aLength); |
|
247 // |
|
248 aDistance--; |
|
249 extralen=0; |
|
250 TUint dist=aDistance; |
|
251 while (dist>=8) |
|
252 { |
|
253 ++extralen; |
|
254 dist>>=1; |
|
255 } |
|
256 OffsetL((extralen<<2)+dist); |
|
257 if (extralen) |
|
258 ExtraL(extralen,aDistance); |
|
259 } |
|
260 |
|
261 // Class TDeflateStats |
|
262 // |
|
263 // This class analyses the data stream to generate the frequency tables |
|
264 // for the deflation algorithm |
|
265 |
|
266 inline TDeflateStats::TDeflateStats(TEncoding& aEncoding) |
|
267 :iEncoding(aEncoding) |
|
268 {} |
|
269 |
|
270 void TDeflateStats::LitLenL(TInt aCode) |
|
271 { |
|
272 ++iEncoding.iLitLen[aCode]; |
|
273 } |
|
274 |
|
275 void TDeflateStats::OffsetL(TInt aCode) |
|
276 { |
|
277 ++iEncoding.iDistance[aCode]; |
|
278 } |
|
279 |
|
280 void TDeflateStats::ExtraL(TInt,TUint) |
|
281 {} |
|
282 |
|
283 // Class TDeflater |
|
284 // |
|
285 // Extends MDeflater to provide huffman encoding of the output |
|
286 |
|
287 inline TDeflater::TDeflater(TBitOutput& aOutput,const TEncoding& aEncoding) |
|
288 // |
|
289 // construct for encoding |
|
290 // |
|
291 :iOutput(aOutput),iEncoding(aEncoding) |
|
292 {} |
|
293 |
|
294 void TDeflater::LitLenL(TInt aCode) |
|
295 { |
|
296 iOutput.HuffmanL(iEncoding.iLitLen[aCode]); |
|
297 } |
|
298 |
|
299 void TDeflater::OffsetL(TInt aCode) |
|
300 { |
|
301 iOutput.HuffmanL(iEncoding.iDistance[aCode]); |
|
302 } |
|
303 |
|
304 void TDeflater::ExtraL(TInt aLen,TUint aBits) |
|
305 { |
|
306 iOutput.WriteL(aBits,aLen); |
|
307 } |
|
308 |
|
309 void DoDeflateL(const TUint8* aBuf,TInt aLength,TBitOutput& aOutput,TEncoding& aEncoding) |
|
310 { |
|
311 // analyse the data for symbol frequency |
|
312 TDeflateStats analyser(aEncoding); |
|
313 analyser.DeflateL(aBuf,aLength); |
|
314 |
|
315 // generate the required huffman encodings |
|
316 Huffman::HuffmanL(aEncoding.iLitLen,TEncoding::ELitLens,aEncoding.iLitLen); |
|
317 Huffman::HuffmanL(aEncoding.iDistance,TEncoding::EDistances,aEncoding.iDistance); |
|
318 |
|
319 // Store the encoding table |
|
320 Huffman::ExternalizeL(aOutput,aEncoding.iLitLen,KDeflationCodes); |
|
321 |
|
322 // generate the tables |
|
323 Huffman::Encoding(aEncoding.iLitLen,TEncoding::ELitLens,aEncoding.iLitLen); |
|
324 Huffman::Encoding(aEncoding.iDistance,TEncoding::EDistances,aEncoding.iDistance); |
|
325 |
|
326 // now finally deflate the data with the generated encoding |
|
327 TDeflater deflater(aOutput,aEncoding); |
|
328 deflater.DeflateL(aBuf,aLength); |
|
329 aOutput.PadL(1); |
|
330 } |
|
331 |
|
332 void DeflateL(const TUint8* aBuf, TInt aLength, TBitOutput& aOutput) |
|
333 { |
|
334 TEncoding* encoding=new TEncoding; |
|
335 HMem::FillZ(encoding,sizeof(TEncoding)); |
|
336 DoDeflateL(aBuf,aLength,aOutput,*encoding); |
|
337 } |
|
338 |