|
1 // Copyright (c) 2002-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 // Name : CDeflate.cpp |
|
15 // Part of : deflatecomp |
|
16 // deflate compressor. |
|
17 // Version : 1.0 |
|
18 // |
|
19 |
|
20 |
|
21 |
|
22 #include <e32base.h> |
|
23 #include <badesca.h> |
|
24 |
|
25 #include "Deflate.h" |
|
26 #include "SigCompDeflateContext.h" |
|
27 #include "MessageWriter.h" |
|
28 |
|
29 /** deflate stream header. btyppe == 01, last block bit set */ |
|
30 static const TInt KDeflateStreamHeaderBits = ((1<<1) + 1); |
|
31 |
|
32 /** number of bits in deflate stream header */ |
|
33 static const TInt KDeflateStreamHeaderBitsLength = 3; |
|
34 |
|
35 |
|
36 /* |
|
37 * Following table is used for length/offset encoding. |
|
38 * as defined in RFC 1951 (DEFLATE Compressed Data Format |
|
39 * Specification version 1.3), chapter 3.2.5. |
|
40 */ |
|
41 const TInt16 KLengthCode[] = |
|
42 { |
|
43 257, 258, 259, 260, 261, 262, 263, 264, 265, 265, 266, 266, 267, 267, |
|
44 268, 268, 269, 269, 269, 269, 270, 270, 270, 270, 271, 271, 271, 271, |
|
45 272, 272, 272, 272, 273, 273, 273, 273, 273, 273, 273, 273, 274, 274, |
|
46 274, 274, 274, 274, 274, 274, 275, 275, 275, 275, 275, 275, 275, 275, |
|
47 276, 276, 276, 276, 276, 276, 276, 276, 277, 277, 277, 277, 277, 277, |
|
48 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 278, 278, 278, 278, |
|
49 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 279, 279, |
|
50 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, |
|
51 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, |
|
52 280, 280, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, |
|
53 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, |
|
54 281, 281, 281, 281, 281, 281, 282, 282, 282, 282, 282, 282, 282, 282, |
|
55 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, |
|
56 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 283, 283, 283, 283, |
|
57 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, |
|
58 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, |
|
59 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, |
|
60 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, |
|
61 284, 284, 284, 285 |
|
62 }; |
|
63 |
|
64 /* |
|
65 * Following table is used for length/offset encoding. |
|
66 * as defined in RFC 1951 (DEFLATE Compressed Data Format |
|
67 * Specification version 1.3), chapter 3.2.5. |
|
68 */ |
|
69 const TUint8 KDistanceCode[] = |
|
70 { |
|
71 0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, |
|
72 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, |
|
73 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, |
|
74 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, |
|
75 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, |
|
76 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, |
|
77 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, |
|
78 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, |
|
79 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, |
|
80 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, |
|
81 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, |
|
82 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, |
|
83 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, |
|
84 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, |
|
85 15, 15, 15, 15, 0, 0, 16, 17, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, |
|
86 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, |
|
87 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, |
|
88 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, |
|
89 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, |
|
90 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, |
|
91 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, |
|
92 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, |
|
93 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, |
|
94 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, |
|
95 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, |
|
96 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, |
|
97 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, |
|
98 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, |
|
99 29, 29, 29, 29, 29, 29, 29, 29 |
|
100 }; |
|
101 |
|
102 /* |
|
103 * Following table is used for length/offset encoding. |
|
104 * as defined in RFC 1951 (DEFLATE Compressed Data Format |
|
105 * Specification version 1.3), chapter 3.2.5. |
|
106 */ |
|
107 const TUint8 KLengthExtraBits[] = |
|
108 { |
|
109 0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0 |
|
110 }; |
|
111 |
|
112 /* |
|
113 * Following table is used for length/offset encoding. |
|
114 * as defined in RFC 1951 (DEFLATE Compressed Data Format |
|
115 * Specification version 1.3), chapter 3.2.5. |
|
116 */ |
|
117 const TUint8 KDistanceExtraBits[] = |
|
118 { |
|
119 0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13 |
|
120 }; |
|
121 |
|
122 /* |
|
123 * Following table is used for length/offset encoding. |
|
124 * as defined in RFC 1951 (DEFLATE Compressed Data Format |
|
125 * Specification version 1.3), chapter 3.2.5. |
|
126 */ |
|
127 const TUint16 KLengthBases[] = |
|
128 { |
|
129 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 28, 32, 40, 48, 56, |
|
130 64, 80, 96, 112, 128, 160, 192, 224, 0 |
|
131 }; |
|
132 |
|
133 /* |
|
134 * Following table is used for length/offset encoding. |
|
135 * as defined in RFC 1951 (DEFLATE Compressed Data Format |
|
136 * Specification version 1.3), chapter 3.2.5. |
|
137 */ |
|
138 const TUint16 KDistanceBases[] = |
|
139 { |
|
140 0, 1, 2, 3, 4, 6, 8, 12, 16, 24, |
|
141 32, 48, 64, 96, 128, 192, 256, 384, 512, 768, |
|
142 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576 |
|
143 }; |
|
144 |
|
145 /** |
|
146 * huffman tree table. Literal tree is used for encoding both literals |
|
147 * and offset/length pairs. |
|
148 * Tables comes from RFC 1951 (DEFLATE Compressed Data Format |
|
149 * Specification version 1.3), chapter 3.2.5. |
|
150 */ |
|
151 const CDeflate::TTreeNode KLiteralTree[] = |
|
152 { |
|
153 { 12, 8}, {140, 8}, { 76, 8}, {204, 8}, { 44, 8}, |
|
154 {172, 8}, {108, 8}, {236, 8}, { 28, 8}, {156, 8}, |
|
155 { 92, 8}, {220, 8}, { 60, 8}, {188, 8}, {124, 8}, |
|
156 {252, 8}, { 2, 8}, {130, 8}, { 66, 8}, {194, 8}, |
|
157 { 34, 8}, {162, 8}, { 98, 8}, {226, 8}, { 18, 8}, |
|
158 {146, 8}, { 82, 8}, {210, 8}, { 50, 8}, {178, 8}, |
|
159 {114, 8}, {242, 8}, { 10, 8}, {138, 8}, { 74, 8}, |
|
160 {202, 8}, { 42, 8}, {170, 8}, {106, 8}, {234, 8}, |
|
161 { 26, 8}, {154, 8}, { 90, 8}, {218, 8}, { 58, 8}, |
|
162 {186, 8}, {122, 8}, {250, 8}, { 6, 8}, {134, 8}, |
|
163 { 70, 8}, {198, 8}, { 38, 8}, {166, 8}, {102, 8}, |
|
164 {230, 8}, { 22, 8}, {150, 8}, { 86, 8}, {214, 8}, |
|
165 { 54, 8}, {182, 8}, {118, 8}, {246, 8}, { 14, 8}, |
|
166 {142, 8}, { 78, 8}, {206, 8}, { 46, 8}, {174, 8}, |
|
167 {110, 8}, {238, 8}, { 30, 8}, {158, 8}, { 94, 8}, |
|
168 {222, 8}, { 62, 8}, {190, 8}, {126, 8}, {254, 8}, |
|
169 { 1, 8}, {129, 8}, { 65, 8}, {193, 8}, { 33, 8}, |
|
170 {161, 8}, { 97, 8}, {225, 8}, { 17, 8}, {145, 8}, |
|
171 { 81, 8}, {209, 8}, { 49, 8}, {177, 8}, {113, 8}, |
|
172 {241, 8}, { 9, 8}, {137, 8}, { 73, 8}, {201, 8}, |
|
173 { 41, 8}, {169, 8}, {105, 8}, {233, 8}, { 25, 8}, |
|
174 {153, 8}, { 89, 8}, {217, 8}, { 57, 8}, {185, 8}, |
|
175 {121, 8}, {249, 8}, { 5, 8}, {133, 8}, { 69, 8}, |
|
176 {197, 8}, { 37, 8}, {165, 8}, {101, 8}, {229, 8}, |
|
177 { 21, 8}, {149, 8}, { 85, 8}, {213, 8}, { 53, 8}, |
|
178 {181, 8}, {117, 8}, {245, 8}, { 13, 8}, {141, 8}, |
|
179 { 77, 8}, {205, 8}, { 45, 8}, {173, 8}, {109, 8}, |
|
180 {237, 8}, { 29, 8}, {157, 8}, { 93, 8}, {221, 8}, |
|
181 { 61, 8}, {189, 8}, {125, 8}, {253, 8}, { 19, 9}, |
|
182 {275, 9}, {147, 9}, {403, 9}, { 83, 9}, {339, 9}, |
|
183 {211, 9}, {467, 9}, { 51, 9}, {307, 9}, {179, 9}, |
|
184 {435, 9}, {115, 9}, {371, 9}, {243, 9}, {499, 9}, |
|
185 { 11, 9}, {267, 9}, {139, 9}, {395, 9}, { 75, 9}, |
|
186 {331, 9}, {203, 9}, {459, 9}, { 43, 9}, {299, 9}, |
|
187 {171, 9}, {427, 9}, {107, 9}, {363, 9}, {235, 9}, |
|
188 {491, 9}, { 27, 9}, {283, 9}, {155, 9}, {411, 9}, |
|
189 { 91, 9}, {347, 9}, {219, 9}, {475, 9}, { 59, 9}, |
|
190 {315, 9}, {187, 9}, {443, 9}, {123, 9}, {379, 9}, |
|
191 {251, 9}, {507, 9}, { 7, 9}, {263, 9}, {135, 9}, |
|
192 {391, 9}, { 71, 9}, {327, 9}, {199, 9}, {455, 9}, |
|
193 { 39, 9}, {295, 9}, {167, 9}, {423, 9}, {103, 9}, |
|
194 {359, 9}, {231, 9}, {487, 9}, { 23, 9}, {279, 9}, |
|
195 {151, 9}, {407, 9}, { 87, 9}, {343, 9}, {215, 9}, |
|
196 {471, 9}, { 55, 9}, {311, 9}, {183, 9}, {439, 9}, |
|
197 {119, 9}, {375, 9}, {247, 9}, {503, 9}, { 15, 9}, |
|
198 {271, 9}, {143, 9}, {399, 9}, { 79, 9}, {335, 9}, |
|
199 {207, 9}, {463, 9}, { 47, 9}, {303, 9}, {175, 9}, |
|
200 {431, 9}, {111, 9}, {367, 9}, {239, 9}, {495, 9}, |
|
201 { 31, 9}, {287, 9}, {159, 9}, {415, 9}, { 95, 9}, |
|
202 {351, 9}, {223, 9}, {479, 9}, { 63, 9}, {319, 9}, |
|
203 {191, 9}, {447, 9}, {127, 9}, {383, 9}, {255, 9}, |
|
204 {511, 9}, { 0, 7}, { 64, 7}, { 32, 7}, { 96, 7}, |
|
205 { 16, 7}, { 80, 7}, { 48, 7}, {112, 7}, { 8, 7}, |
|
206 { 72, 7}, { 40, 7}, {104, 7}, { 24, 7}, { 88, 7}, |
|
207 { 56, 7}, {120, 7}, { 4, 7}, { 68, 7}, { 36, 7}, |
|
208 {100, 7}, { 20, 7}, { 84, 7}, { 52, 7}, {116, 7}, |
|
209 { 3, 8}, {131, 8}, { 67, 8}, {195, 8}, { 35, 8}, |
|
210 {163, 8}, { 99, 8}, {227, 8} |
|
211 }; |
|
212 |
|
213 /** |
|
214 * huffman tree table. Distance tree is used for encoding distance. |
|
215 * Tables comes from RFC 1951 (DEFLATE Compressed Data Format |
|
216 * Specification version 1.3), chapter 3.2.5. |
|
217 */ |
|
218 const CDeflate::TTreeNode KDistanceTree[] = |
|
219 { |
|
220 { 0, 5}, {16, 5}, { 8, 5}, {24, 5}, { 4, 5}, |
|
221 {20, 5}, {12, 5}, {28, 5}, { 2, 5}, {18, 5}, |
|
222 {10, 5}, {26, 5}, { 6, 5}, {22, 5}, {14, 5}, |
|
223 {30, 5}, { 1, 5}, {17, 5}, { 9, 5}, {25, 5}, |
|
224 { 5, 5}, {21, 5}, {13, 5}, {29, 5}, { 3, 5}, |
|
225 {19, 5}, {11, 5}, {27, 5}, { 7, 5}, {23, 5} |
|
226 }; |
|
227 |
|
228 CDeflate* CDeflate::NewL(TBool aDynamic, CSigCompDeflateContext* aContext) |
|
229 { |
|
230 CDeflate* self= NewLC(aDynamic, aContext); |
|
231 CleanupStack::Pop(); |
|
232 return self; |
|
233 } |
|
234 |
|
235 CDeflate* CDeflate::NewLC(TBool aDynamic, CSigCompDeflateContext* aContext) |
|
236 { |
|
237 CDeflate* self= new (ELeave) CDeflate(); |
|
238 CleanupStack::PushL(self); |
|
239 self->ConstructL(aDynamic, aContext); |
|
240 return self; |
|
241 } |
|
242 |
|
243 CDeflate::~CDeflate() |
|
244 { |
|
245 delete iHashTable; |
|
246 delete iChainNodes; |
|
247 } |
|
248 |
|
249 void CDeflate::CompressL(const TDesC8& aMessage, |
|
250 CMessageWriter* aMessageWriter) |
|
251 { |
|
252 iMessageWriter = aMessageWriter; |
|
253 CArrayFixFlat<TUint8>* window = iDeflateContext->Window(); |
|
254 |
|
255 SendBitsL(KDeflateStreamHeaderBits, |
|
256 KDeflateStreamHeaderBitsLength); |
|
257 |
|
258 const TUint8* msgPtr = aMessage.Ptr(); |
|
259 TInt msgSize = aMessage.Length(); |
|
260 TInt processed = 0; |
|
261 while (processed < msgSize) |
|
262 { |
|
263 processed += FillWindow(msgPtr + processed, msgSize - processed); |
|
264 |
|
265 while (iLookAhead) |
|
266 { |
|
267 TInt position; |
|
268 TInt length; |
|
269 TInt currentPosition; |
|
270 if (FindBestMatch(position, length)) |
|
271 { |
|
272 //lazy matching: |
|
273 if ( length < KNiceLazyMatchLength ) |
|
274 { |
|
275 currentPosition = iDeflateContext->CurrentPosition(); |
|
276 currentPosition++; |
|
277 iDeflateContext->SetCurrentPosition(currentPosition); |
|
278 TInt lazyPosition; |
|
279 TInt lazyLength; |
|
280 if (FindBestMatch(lazyPosition, lazyLength)) |
|
281 { |
|
282 if (lazyLength > length) |
|
283 { |
|
284 InsertHash(iDeflateContext->CurrentPosition() - 1); |
|
285 EncodeLiteralL( |
|
286 window->At(iDeflateContext->CurrentPosition() - 1)); |
|
287 iLookAhead--; |
|
288 length = lazyLength; |
|
289 position = lazyPosition; |
|
290 } |
|
291 else |
|
292 { |
|
293 currentPosition = iDeflateContext->CurrentPosition(); |
|
294 currentPosition--; |
|
295 iDeflateContext->SetCurrentPosition(currentPosition); |
|
296 } |
|
297 } |
|
298 else |
|
299 { |
|
300 currentPosition = iDeflateContext->CurrentPosition(); |
|
301 currentPosition--; |
|
302 iDeflateContext->SetCurrentPosition(currentPosition); |
|
303 } |
|
304 } |
|
305 EncodeDistanceLengthPairL(iDeflateContext->CurrentPosition() - |
|
306 position, length); |
|
307 iLookAhead -= length; |
|
308 while (length--) |
|
309 { |
|
310 InsertHash(iDeflateContext->CurrentPosition()); |
|
311 currentPosition = iDeflateContext->CurrentPosition(); |
|
312 currentPosition++; |
|
313 iDeflateContext->SetCurrentPosition(currentPosition); |
|
314 } |
|
315 } |
|
316 else |
|
317 { |
|
318 InsertHash(iDeflateContext->CurrentPosition()); |
|
319 EncodeLiteralL(window->At(iDeflateContext->CurrentPosition())); |
|
320 currentPosition = iDeflateContext->CurrentPosition(); |
|
321 currentPosition++; |
|
322 iDeflateContext->SetCurrentPosition(currentPosition); |
|
323 iLookAhead--; |
|
324 } |
|
325 } |
|
326 } |
|
327 |
|
328 EncodeLiteralL(256); |
|
329 FlushBitsL(); |
|
330 } |
|
331 |
|
332 void CDeflate::Reset(void) |
|
333 { |
|
334 iDeflateContext->SetCurrentPosition(0); |
|
335 iLookAhead = 0; |
|
336 ResetHashTable(); |
|
337 iBitBuffer = 0; |
|
338 iBitsQueued = 0; |
|
339 } |
|
340 |
|
341 void CDeflate::ResetHashTable(void) |
|
342 { |
|
343 |
|
344 TInt i; |
|
345 if (iHashTable) |
|
346 { |
|
347 for (i = 0;i < iHashSize;i++) |
|
348 { |
|
349 (*iHashTable)[i] = 0; |
|
350 } |
|
351 } |
|
352 |
|
353 if (iChainNodes) |
|
354 { |
|
355 for (i = 0;i < iDeflateContext->WindowSize();i++) |
|
356 { |
|
357 (*iChainNodes)[i] = 0; |
|
358 } |
|
359 } |
|
360 } |
|
361 |
|
362 void CDeflate::SetDictionary(const TUint8* aPtr, TInt aSize) |
|
363 { |
|
364 if (aPtr) |
|
365 { |
|
366 ResetHashTable(); |
|
367 Mem::Copy(&iDeflateContext->Window()->At(0), aPtr, aSize); |
|
368 |
|
369 for (TInt i = 0;i < aSize - 2;i++) |
|
370 { |
|
371 InsertHash(i); |
|
372 } |
|
373 iDeflateContext->SetCurrentPosition(aSize); |
|
374 } |
|
375 } |
|
376 |
|
377 void CDeflate::ChangeWindowSizeL(TInt aWindowSize) |
|
378 { |
|
379 if (aWindowSize != iDeflateContext->WindowSize()) |
|
380 { |
|
381 iDeflateContext->SetWindowSize(aWindowSize); |
|
382 |
|
383 CArrayFixFlat<TUint8>* window = new (ELeave)CArrayFixFlat<TUint8>(8); |
|
384 iDeflateContext->SetWindow(window); |
|
385 iDeflateContext->Window()->ResizeL(iDeflateContext->WindowSize() * 2); |
|
386 |
|
387 delete iChainNodes; |
|
388 iChainNodes = NULL; |
|
389 iChainNodes = new (ELeave)CArrayFixFlat<TInt16>(8); |
|
390 iChainNodes->ResizeL(iDeflateContext->WindowSize()); |
|
391 iChainMask = iDeflateContext->WindowSize() - 1; |
|
392 |
|
393 ResetHashTable(); |
|
394 iDeflateContext->SetCurrentPosition(0); |
|
395 iLookAhead = 0; |
|
396 } |
|
397 } |
|
398 |
|
399 void CDeflate::SendBitsL(TUint aValue, TUint aLength) |
|
400 { |
|
401 iBitBuffer |= aValue << iBitsQueued; |
|
402 iBitsQueued += aLength; |
|
403 while (iBitsQueued >= 8) |
|
404 { |
|
405 PutByteL(static_cast<TUint8>(iBitBuffer & 0xff)); |
|
406 iBitBuffer >>= 8; |
|
407 iBitsQueued -= 8; |
|
408 } |
|
409 } |
|
410 |
|
411 void CDeflate::FlushBitsL() |
|
412 { |
|
413 if (iBitsQueued > 0) |
|
414 { |
|
415 PutByteL(static_cast<TUint8>(iBitBuffer)); |
|
416 } |
|
417 iBitBuffer = 0; |
|
418 iBitsQueued = 0; |
|
419 } |
|
420 |
|
421 void CDeflate::PutByteL(TUint8 aByte) |
|
422 { |
|
423 iMessageWriter->WriteByteL(aByte); |
|
424 } |
|
425 |
|
426 void CDeflate::EncodeLiteralL(TInt aCode) |
|
427 { |
|
428 SendBitsL(KLiteralTree[aCode].iBits, KLiteralTree[aCode].iLength); |
|
429 } |
|
430 |
|
431 void CDeflate::EncodeDistanceLengthPairL(TUint aDist, TUint aLength) |
|
432 { |
|
433 aLength -= KMinMatch; |
|
434 aDist -= 1; |
|
435 |
|
436 TInt code = KLengthCode[aLength]; |
|
437 EncodeLiteralL(code); |
|
438 TUint extra = KLengthExtraBits[code - (KMaxMatch - 1)]; |
|
439 if (extra) |
|
440 { |
|
441 aLength -= KLengthBases[code - (KMaxMatch - 1)]; |
|
442 SendBitsL(aLength, extra); |
|
443 } |
|
444 |
|
445 if (aDist < KEncodeDistance) |
|
446 { |
|
447 code = KDistanceCode[aDist]; |
|
448 } |
|
449 else |
|
450 { |
|
451 code = KDistanceCode[(aDist>>7) + KEncodeDistance]; |
|
452 } |
|
453 |
|
454 SendBitsL(KDistanceTree[code].iBits, KDistanceTree[code].iLength); |
|
455 |
|
456 extra = KDistanceExtraBits[code]; |
|
457 if (extra) |
|
458 { |
|
459 aDist -= KDistanceBases[code]; |
|
460 SendBitsL(aDist, extra); |
|
461 } |
|
462 } |
|
463 |
|
464 TBool CDeflate::FindBestMatch(TInt& aMatchPos, TInt& aLength) |
|
465 { |
|
466 aMatchPos = 0; |
|
467 if (iLookAhead > KMinMatch) |
|
468 { |
|
469 TInt position = iDeflateContext->CurrentPosition(); |
|
470 TInt16 currentPos = (*iHashTable)[CalcHash( |
|
471 iDeflateContext->Window()->At(position), |
|
472 iDeflateContext->Window()->At(position + 1), |
|
473 iDeflateContext->Window()->At(position + 2))]; |
|
474 TInt chainLength = KMaxChainLength; |
|
475 aLength = KMinMatch - 1; |
|
476 |
|
477 while (currentPos && chainLength > 0) |
|
478 { |
|
479 TInt len = 0; |
|
480 TUint8 *m = &iDeflateContext->Window()->At(position); |
|
481 TUint8 *c = &iDeflateContext->Window()->At(currentPos); |
|
482 while ((len < Min(KMaxMatch, iLookAhead)) && |
|
483 ((position + len) < (2 * iDeflateContext->WindowSize())) && |
|
484 (*m++ == *c++)) |
|
485 { |
|
486 len++; |
|
487 } |
|
488 |
|
489 if ((len > aLength) && |
|
490 ((position - currentPos) < iDeflateContext->WindowSize())) |
|
491 { |
|
492 aMatchPos = currentPos; |
|
493 aLength = len; |
|
494 if ( aLength >= KGoodMatchLength ) |
|
495 break; |
|
496 } |
|
497 |
|
498 if ( aLength >= KNiceMatchLength ) |
|
499 chainLength >>= 2; |
|
500 |
|
501 currentPos = (*iChainNodes)[currentPos & iChainMask]; |
|
502 chainLength--; |
|
503 } |
|
504 } |
|
505 return (aMatchPos > 0) ? ETrue : EFalse; |
|
506 } |
|
507 |
|
508 TInt CDeflate::FillWindow(const TUint8* aPtr, TInt aBytes) |
|
509 { |
|
510 TInt position = iDeflateContext->CurrentPosition(); |
|
511 TInt processed = Min(aBytes, 2 * iDeflateContext->WindowSize() - |
|
512 (position + iLookAhead)); |
|
513 |
|
514 if (position >= (2 * iDeflateContext->WindowSize() - KMaxMatch)) |
|
515 { |
|
516 Mem::Copy(&iDeflateContext->Window()->At(0), |
|
517 &iDeflateContext->Window()->At(iDeflateContext->WindowSize()), |
|
518 iDeflateContext->WindowSize()); |
|
519 position -= iDeflateContext->WindowSize(); |
|
520 iDeflateContext->SetCurrentPosition(position); |
|
521 |
|
522 TInt i; |
|
523 for (i=0; i<iHashSize; i++) |
|
524 { |
|
525 TInt16 t = (*iHashTable)[i]; |
|
526 t = static_cast<TInt16>((t > iDeflateContext->WindowSize()) ? |
|
527 (t - iDeflateContext->WindowSize()) : 0); |
|
528 (*iHashTable)[i] = t; |
|
529 } |
|
530 |
|
531 for (i=0; i<iDeflateContext->WindowSize(); i++) |
|
532 { |
|
533 TInt16 t = (*iChainNodes)[i]; |
|
534 t = static_cast<TInt16>((t > iDeflateContext->WindowSize()) ? |
|
535 (t - iDeflateContext->WindowSize()) : 0); |
|
536 (*iChainNodes)[i] = t; |
|
537 } |
|
538 |
|
539 processed = Min(processed + iDeflateContext->WindowSize(), aBytes); |
|
540 } |
|
541 |
|
542 Mem::Copy(&iDeflateContext->Window()->At(position + iLookAhead), |
|
543 aPtr, processed); |
|
544 iLookAhead += processed; |
|
545 return processed; |
|
546 } |
|
547 |
|
548 void CDeflate::InsertHash(TInt aPosition) |
|
549 { |
|
550 if ((aPosition + 2) < 2 * (iDeflateContext->WindowSize())) |
|
551 { |
|
552 TUint hash = CalcHash(iDeflateContext->Window()->At(aPosition), |
|
553 iDeflateContext->Window()->At(aPosition + 1), |
|
554 iDeflateContext->Window()->At(aPosition + 2)); |
|
555 (*iChainNodes)[aPosition & iChainMask] = (*iHashTable)[hash]; |
|
556 (*iHashTable)[hash] = static_cast<TInt16>(aPosition); |
|
557 } |
|
558 } |
|
559 |
|
560 TInt CDeflate::CalcHash(TUint8 aA, TUint8 aB, TUint8 aC) const |
|
561 { |
|
562 return (((aA << (iHashShift2)) ^ (aB << iHashShift) ^ aC) & iHashMask); |
|
563 } |
|
564 |
|
565 void CDeflate::ConstructL(TBool aDynamic, CSigCompDeflateContext* aContext) |
|
566 { |
|
567 iDynamic = aDynamic; |
|
568 iDeflateContext = aContext; |
|
569 |
|
570 iHashSize = 1 << KHashTableBits; |
|
571 iHashMask = iHashSize - 1; |
|
572 iHashShift = ((KHashTableBits + KMinMatch - 1) / KMinMatch); |
|
573 iHashShift2 = iHashShift << 1; |
|
574 iHashTable = new (ELeave)CArrayFixFlat<TInt16>(8); |
|
575 iHashTable->ResizeL(iHashSize); |
|
576 |
|
577 if (iDeflateContext->Window() != NULL) |
|
578 { |
|
579 iChainNodes = new (ELeave)CArrayFixFlat<TInt16>(8); |
|
580 iChainNodes->ResizeL(iDeflateContext->WindowSize()); |
|
581 iChainMask = iDeflateContext->WindowSize() - 1; |
|
582 |
|
583 ResetHashTable(); |
|
584 iLookAhead = 0; |
|
585 |
|
586 if (iDynamic) |
|
587 { |
|
588 TInt position = aContext->CurrentPosition(); |
|
589 |
|
590 if (position > 2) |
|
591 { |
|
592 for (TInt i = 0;i < position - 2;i++) |
|
593 { |
|
594 InsertHash(i); |
|
595 } |
|
596 } |
|
597 } |
|
598 else |
|
599 { |
|
600 iDeflateContext->SetCurrentPosition(0); |
|
601 } |
|
602 } |
|
603 else |
|
604 { |
|
605 iDeflateContext->SetWindowSize(0); |
|
606 } |
|
607 } |
|
608 |
|
609 CDeflate::CDeflate() |
|
610 { |
|
611 } |