|
1 // Copyright (c) 2004-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 the License "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 // Implementation of the Huffman technique for the elf2e32 tool |
|
15 // @internalComponent |
|
16 // @released |
|
17 // |
|
18 // |
|
19 |
|
20 #ifdef _MSC_VER |
|
21 #pragma warning(disable: 4710) // function not inlined |
|
22 #endif |
|
23 |
|
24 #include <cassert> |
|
25 #include "huffman.h" |
|
26 #include "errorhandler.h" |
|
27 #include "farray.h" |
|
28 |
|
29 /** |
|
30 Function for overflow |
|
31 @internalComponent |
|
32 @released |
|
33 */ |
|
34 void TBitOutput::OverflowL() |
|
35 { |
|
36 } |
|
37 |
|
38 /** |
|
39 Construct a bit stream output object |
|
40 |
|
41 Following construction the bit stream is ready for writing bits, but will first call |
|
42 OverflowL() as the output buffer is 'full'. A derived class can detect this state as |
|
43 Ptr() will return null. |
|
44 */ |
|
45 TBitOutput::TBitOutput():iCode(0),iBits(-8),iPtr(0),iEnd(0) |
|
46 { |
|
47 } |
|
48 |
|
49 /** |
|
50 Construct a bit stream output object over a buffer |
|
51 |
|
52 Data will be written to the buffer until it is full, at which point OverflowL() will |
|
53 be called. This should handle the data and then can Set() again to reset the buffer |
|
54 for further output. |
|
55 |
|
56 @param "TUint8* aBuf" The buffer for output |
|
57 @param "TInt aSize" The size of the buffer in bytes |
|
58 */ |
|
59 TBitOutput::TBitOutput(TUint8* aBuf,TInt aSize):iCode(0),iBits(-8),iPtr(aBuf),iEnd(aBuf+aSize) |
|
60 { |
|
61 } |
|
62 |
|
63 /** |
|
64 Write a huffman code |
|
65 |
|
66 This expects a huffman code value as generated by Huffman::Encoding() |
|
67 |
|
68 @param "TUint aHuffCode" The huffman code write to the stream |
|
69 @leave "OverflowL()" If the output buffer is full, OverflowL() is called |
|
70 */ |
|
71 void TBitOutput::HuffmanL(TUint aHuffCode) |
|
72 { |
|
73 DoWriteL(aHuffCode<<(32-Huffman::KMaxCodeLength),aHuffCode>>Huffman::KMaxCodeLength); |
|
74 } |
|
75 |
|
76 /** |
|
77 Write an arbitrary integer value |
|
78 |
|
79 Write an unsigned integer using the number of bits specified. Only the low order bits of the |
|
80 value are written to the output, most significant bit first. |
|
81 |
|
82 @param "TUint aValue" The value to write to the stream |
|
83 @param "TUint aLength" The number of bits to output |
|
84 @leave "OverflowL()" If the output buffer is full, OverflowL() is called |
|
85 */ |
|
86 void TBitOutput::WriteL(TUint aValue,TInt aLength) |
|
87 { |
|
88 if (aLength) |
|
89 DoWriteL(aValue<<=32-aLength,aLength); |
|
90 } |
|
91 |
|
92 /** |
|
93 Pad the bitstream to the next byte boundary |
|
94 |
|
95 Terminate the bitstream by padding the last byte with the requested value. |
|
96 Following this operation the bitstream can continue to be used, the data will start at the |
|
97 next byte. |
|
98 |
|
99 @param "TUint aPadding" The bit value to pad the final byte with |
|
100 @leave "OverflowL()" If the output buffer is full, OverflowL() is called |
|
101 */ |
|
102 void TBitOutput::PadL(TUint aPadding) |
|
103 { |
|
104 if (iBits>-8) |
|
105 WriteL(aPadding?0xffffffffu:0,-iBits); |
|
106 } |
|
107 |
|
108 /** |
|
109 Write the higher order bits to the stream |
|
110 @internalComponent |
|
111 @released |
|
112 */ |
|
113 void TBitOutput::DoWriteL(TUint aBits,TInt aSize) |
|
114 { |
|
115 if (aSize>25) |
|
116 { |
|
117 // cannot process >25 bits in a single pass so do the top 8 bits first |
|
118 assert(aSize<=32); |
|
119 DoWriteL(aBits&0xff000000u,8); |
|
120 aBits<<=8; |
|
121 aSize-=8; |
|
122 } |
|
123 |
|
124 TInt bits=iBits; |
|
125 TUint code=iCode|(aBits>>(bits+8)); |
|
126 bits+=aSize; |
|
127 if (bits>=0) |
|
128 { |
|
129 TUint8* p=iPtr; |
|
130 do |
|
131 { |
|
132 if (p==iEnd) |
|
133 { |
|
134 // run out of buffer space so invoke the overflow handler |
|
135 iPtr=p; |
|
136 OverflowL(); |
|
137 p=iPtr; |
|
138 assert(p!=iEnd); |
|
139 } |
|
140 *p++=TUint8(code>>24); |
|
141 code<<=8; |
|
142 bits-=8; |
|
143 } while (bits>=0); |
|
144 iPtr=p; |
|
145 } |
|
146 iCode=code; |
|
147 iBits=bits; |
|
148 } |
|
149 |
|
150 /** |
|
151 Constructor for class TFileOutput |
|
152 @internalComponent |
|
153 @released |
|
154 */ |
|
155 TFileOutput::TFileOutput(std::ofstream & os):iOutStream(os) |
|
156 { |
|
157 Set(iBuf,KBufSize); |
|
158 } |
|
159 |
|
160 /** |
|
161 Function to empty the buffer and reset the pointers |
|
162 @internalComponent |
|
163 @released |
|
164 */ |
|
165 void TFileOutput::OverflowL() |
|
166 { |
|
167 FlushL(); |
|
168 Set(iBuf,KBufSize); |
|
169 } |
|
170 |
|
171 /** |
|
172 Function to write out the contents of the buffer |
|
173 @internalComponent |
|
174 @released |
|
175 */ |
|
176 void TFileOutput::FlushL() |
|
177 { |
|
178 TInt len=Ptr()-iBuf; |
|
179 if (len) |
|
180 { |
|
181 iOutStream.write(reinterpret_cast<char *>(iBuf), len); // write extended header |
|
182 iDataCount += len; |
|
183 } |
|
184 } |
|
185 |
|
186 /** |
|
187 Recursive function to calculate the code lengths from the node tree |
|
188 @internalComponent |
|
189 @released |
|
190 */ |
|
191 void HuffmanLengthsL(TUint32* aLengths,const TNode* aNodes,TInt aNode,TInt aLen) |
|
192 { |
|
193 if (++aLen>Huffman::KMaxCodeLength) |
|
194 throw E32ImageCompressionError(HUFFMANBUFFEROVERFLOWERROR); |
|
195 |
|
196 const TNode& node=aNodes[aNode]; |
|
197 TUint x=node.iLeft; |
|
198 if (x&KLeaf) |
|
199 aLengths[x&~KLeaf]=aLen; |
|
200 else |
|
201 HuffmanLengthsL(aLengths,aNodes,x,aLen); |
|
202 x=node.iRight; |
|
203 if (x&KLeaf) |
|
204 aLengths[x&~KLeaf]=aLen; |
|
205 else |
|
206 HuffmanLengthsL(aLengths,aNodes,x,aLen); |
|
207 } |
|
208 |
|
209 /** |
|
210 Function to Insert the {aCount,aValue} pair into the already sorted array of nodes |
|
211 @internalComponent |
|
212 @released |
|
213 */ |
|
214 void InsertInOrder(TNode* aNodes, TInt aSize, TUint aCount, TInt aVal) |
|
215 { |
|
216 // Uses Insertion sort following a binary search... |
|
217 TInt l=0, r=aSize; |
|
218 while (l < r) |
|
219 { |
|
220 TInt m = (l+r) >> 1; |
|
221 if (aNodes[m].iCount<aCount) |
|
222 r=m; |
|
223 else |
|
224 l=m+1; |
|
225 } |
|
226 memmove(aNodes+l+1,aNodes+l,sizeof(TNode)*(aSize-l)); |
|
227 aNodes[l].iCount=aCount; |
|
228 aNodes[l].iRight=TUint16(aVal); |
|
229 } |
|
230 |
|
231 /** |
|
232 Generate a Huffman code. |
|
233 |
|
234 This generates a Huffman code for a given set of code frequencies. The output is a table of |
|
235 code lengths which can be used to build canonincal encoding tables or decoding trees for use |
|
236 with the TBitInput and TBitOutput classes. |
|
237 |
|
238 Entries in the table with a frequency of zero will have a zero code length and thus no |
|
239 associated huffman encoding. If each such symbol should have a maximum length encoding, they |
|
240 must be given at least a frequency of 1. |
|
241 |
|
242 For an alphabet of n symbols, this algorithm has a transient memory overhead of 8n, and a |
|
243 time complexity of O(n*log(n)). |
|
244 |
|
245 @param "const TUint32 aFrequency[]" The table of code frequencies |
|
246 @param "TInt aNumCodes" The number of codes in the table |
|
247 @param "TUint32 aHuffman[]" The table for the output code-length table. This must be the same |
|
248 size as the frequency table, and can safely be the same table |
|
249 |
|
250 @leave "KErrNoMemory" If memory used for code generation cannot be allocated |
|
251 @panic "USER ???" If the number of codes exceeds Huffman::KMaxCodes |
|
252 */ |
|
253 void Huffman::HuffmanL(const TUint32 aFrequency[],TInt aNumCodes,TUint32 aHuffman[]) |
|
254 { |
|
255 if(TUint(aNumCodes)>TUint(KMaxCodes)) |
|
256 throw E32ImageCompressionError(HUFFMANTOOMANYCODESERROR); |
|
257 |
|
258 // Sort the values into decreasing order of frequency |
|
259 TNode* nodes = new TNode[aNumCodes]; |
|
260 |
|
261 TInt lCount=0; |
|
262 |
|
263 for (TInt ii=0;ii<aNumCodes;++ii) |
|
264 { |
|
265 TInt c=aFrequency[ii]; |
|
266 if (c!=0) |
|
267 InsertInOrder(nodes,lCount++,c,ii|KLeaf); |
|
268 } |
|
269 |
|
270 // default code length is zero |
|
271 memset(aHuffman,0,aNumCodes*sizeof(TUint32)); |
|
272 |
|
273 if (lCount==0) |
|
274 { |
|
275 // no codes with frequency>0. No code has a length |
|
276 } |
|
277 else if (lCount==1) |
|
278 { |
|
279 // special case for a single value (always encode as "0") |
|
280 aHuffman[nodes[0].iRight&~KLeaf]=1; |
|
281 } |
|
282 else |
|
283 { |
|
284 // Huffman algorithm: pair off least frequent nodes and reorder |
|
285 do |
|
286 { |
|
287 --lCount; |
|
288 TUint c=nodes[lCount].iCount + nodes[lCount-1].iCount; |
|
289 nodes[lCount].iLeft=nodes[lCount-1].iRight; |
|
290 // re-order the leaves now to reflect new combined frequency 'c' |
|
291 InsertInOrder(nodes,lCount-1,c,lCount); |
|
292 } while (lCount>1); |
|
293 // generate code lengths in aHuffman[] |
|
294 HuffmanLengthsL(aHuffman,nodes,1,0); |
|
295 } |
|
296 |
|
297 delete [] nodes; |
|
298 |
|
299 if(!IsValid(aHuffman,aNumCodes)) |
|
300 throw E32ImageCompressionError(HUFFMANINVALIDCODINGERROR); |
|
301 } |
|
302 |
|
303 /** |
|
304 Validate a Huffman encoding |
|
305 |
|
306 This verifies that a Huffman coding described by the code lengths is valid. In particular, |
|
307 it ensures that no code exceeds the maximum length and that it is possible to generate a |
|
308 canonical coding for the specified lengths. |
|
309 |
|
310 @param "const TUint32 aHuffman[]" The table of code lengths as generated by Huffman::HuffmanL() |
|
311 @param "TInt aNumCodes" The number of codes in the table |
|
312 |
|
313 @return True if the code is valid, otherwise false |
|
314 */ |
|
315 TBool Huffman::IsValid(const TUint32 aHuffman[],TInt aNumCodes) |
|
316 { |
|
317 // The code is valid if one of the following holds: |
|
318 // (a) the code exactly fills the 'code space' |
|
319 // (b) there is only a single symbol with code length 1 |
|
320 // (c) there are no encoded symbols |
|
321 // |
|
322 TUint remain=1<<KMaxCodeLength; |
|
323 TInt totlen=0; |
|
324 for (const TUint32* p=aHuffman+aNumCodes; p>aHuffman;) |
|
325 { |
|
326 TInt len=*--p; |
|
327 if (len>0) |
|
328 { |
|
329 totlen+=len; |
|
330 if (len>KMaxCodeLength) |
|
331 return 0; |
|
332 |
|
333 TUint c=1<<(KMaxCodeLength-len); |
|
334 if (c>remain) |
|
335 return 0; |
|
336 |
|
337 remain-=c; |
|
338 } |
|
339 } |
|
340 |
|
341 return remain==0 || totlen<=1; |
|
342 } |
|
343 |
|
344 /** |
|
345 Create a canonical Huffman encoding table |
|
346 |
|
347 This generates the huffman codes used by TBitOutput::HuffmanL() to write huffman encoded data. |
|
348 The input is table of code lengths, as generated by Huffman::HuffmanL() and must represent a |
|
349 valid huffman code. |
|
350 |
|
351 @param "const TUint32 aHuffman[]" The table of code lengths as generated by Huffman::HuffmanL() |
|
352 @param "TInt aNumCodes" The number of codes in the table |
|
353 @param "TUint32 aEncodeTable[]" The table for the output huffman codes. This must be the same |
|
354 size as the code-length table, and can safely be the same table. |
|
355 |
|
356 @panic "USER ???" If the provided code is not a valid Huffman coding |
|
357 |
|
358 @see IsValid() |
|
359 @see HuffmanL() |
|
360 */ |
|
361 void Huffman::Encoding(const TUint32 aHuffman[],TInt aNumCodes,TUint32 aEncodeTable[]) |
|
362 { |
|
363 if (!IsValid(aHuffman,aNumCodes)) |
|
364 throw E32ImageCompressionError(HUFFMANINVALIDCODINGERROR); |
|
365 |
|
366 TFixedArray<TInt,KMaxCodeLength> lenCount; |
|
367 lenCount.Reset(); |
|
368 |
|
369 TInt ii; |
|
370 for (ii=0;ii<aNumCodes;++ii) |
|
371 { |
|
372 TInt len=aHuffman[ii]-1; |
|
373 if (len>=0) |
|
374 ++lenCount[len]; |
|
375 } |
|
376 |
|
377 TFixedArray<TUint,KMaxCodeLength> nextCode; |
|
378 TUint code=0; |
|
379 for (ii=0;ii<KMaxCodeLength;++ii) |
|
380 { |
|
381 code<<=1; |
|
382 nextCode[ii]=code; |
|
383 code+=lenCount[ii]; |
|
384 } |
|
385 |
|
386 for (ii=0;ii<aNumCodes;++ii) |
|
387 { |
|
388 TInt len=aHuffman[ii]; |
|
389 if (len==0) |
|
390 aEncodeTable[ii]=0; |
|
391 else |
|
392 { |
|
393 aEncodeTable[ii] = (nextCode[len-1]<<(KMaxCodeLength-len))|(len<<KMaxCodeLength); |
|
394 ++nextCode[len-1]; |
|
395 } |
|
396 } |
|
397 } |
|
398 |
|
399 /** |
|
400 The encoding table for the externalised code |
|
401 @internalComponent |
|
402 @released |
|
403 */ |
|
404 const TUint32 HuffmanEncoding[]= |
|
405 { |
|
406 0x10000000, |
|
407 0x1c000000, |
|
408 0x12000000, |
|
409 0x1d000000, |
|
410 0x26000000, |
|
411 0x26800000, |
|
412 0x2f000000, |
|
413 0x37400000, |
|
414 0x37600000, |
|
415 0x37800000, |
|
416 0x3fa00000, |
|
417 0x3fb00000, |
|
418 0x3fc00000, |
|
419 0x3fd00000, |
|
420 0x47e00000, |
|
421 0x47e80000, |
|
422 0x47f00000, |
|
423 0x4ff80000, |
|
424 0x57fc0000, |
|
425 0x5ffe0000, |
|
426 0x67ff0000, |
|
427 0x77ff8000, |
|
428 0x7fffa000, |
|
429 0x7fffb000, |
|
430 0x7fffc000, |
|
431 0x7fffd000, |
|
432 0x7fffe000, |
|
433 0x87fff000, |
|
434 0x87fff800 |
|
435 }; |
|
436 |
|
437 /** |
|
438 Function to encode 0a as '0' and 0b as '1', return number of symbols created |
|
439 @internalComponent |
|
440 @released |
|
441 */ |
|
442 void EncodeRunLengthL(TBitOutput& aOutput, TInt aLength) |
|
443 { |
|
444 if (aLength>0) |
|
445 { |
|
446 EncodeRunLengthL(aOutput,(aLength-1)>>1); |
|
447 aOutput.HuffmanL(HuffmanEncoding[1-(aLength&1)]); |
|
448 } |
|
449 } |
|
450 |
|
451 /** |
|
452 Store a canonical huffman encoding in compact form |
|
453 |
|
454 As the encoding is canonical, only the code lengths of each code needs to be saved. |
|
455 |
|
456 Due to the nature of code length tables, these can usually be stored very compactly by |
|
457 encoding the encoding itself, hence the use of the bit output stream. |
|
458 |
|
459 @param "TBitOutput& aOutput" The output stream for the encoding |
|
460 @param "const TUint32 aHuffman[]" The table of code lengths as generated by Huffman::HuffmanL() |
|
461 @param "TInt aNumCodes" The number of huffman codes in the table |
|
462 |
|
463 @leave "TBitOutput::HuffmanL()" |
|
464 */ |
|
465 void Huffman::ExternalizeL(TBitOutput& aOutput,const TUint32 aHuffman[],TInt aNumCodes) |
|
466 { |
|
467 // We assume that the code length table is generated by the huffman generator, |
|
468 // in which case the maxmimum code length is 27 bits. |
|
469 // |
|
470 // We apply three transformations to the data: |
|
471 // 1. the data goes through a move-to-front coder |
|
472 // 2. apply a rle-0 coder which replace runs of '0' with streams of '0a' and '0b' |
|
473 // 3. encode the result using a predefined (average) huffman coding |
|
474 // |
|
475 // This can be done in a single pass over the data, avoiding the need for additional |
|
476 // memory. |
|
477 // |
|
478 // initialise the list for the MTF coder |
|
479 TFixedArray<TUint8,Huffman::KMetaCodes> list; |
|
480 TInt i; |
|
481 for (i=0;i<list.Count();++i) |
|
482 list[i]=TUint8(i); |
|
483 TInt last=0; |
|
484 |
|
485 TInt rl=0; |
|
486 const TUint32* p32=aHuffman; |
|
487 const TUint32* e32=p32+aNumCodes; |
|
488 while (p32<e32) |
|
489 { |
|
490 TInt c=*p32++; |
|
491 if (c==last) |
|
492 ++rl; // repeat of last symbol |
|
493 else |
|
494 { |
|
495 // encode run-length |
|
496 EncodeRunLengthL(aOutput,rl); |
|
497 rl=0; |
|
498 // find code in MTF list |
|
499 TInt j; |
|
500 for (j=1;list[j]!=c;++j) |
|
501 ; |
|
502 // store this code |
|
503 aOutput.HuffmanL(HuffmanEncoding[j+1]); |
|
504 // adjust list for MTF algorithm |
|
505 while (--j>0) |
|
506 list[j+1]=list[j]; |
|
507 list[1]=TUint8(last); |
|
508 last=c; |
|
509 } |
|
510 } |
|
511 // encod any remaining run-length |
|
512 EncodeRunLengthL(aOutput,rl); |
|
513 } |
|
514 |
|
515 const TInt KHuffTerminate=0x0001; |
|
516 const TUint32 KBranch1=sizeof(TUint32)<<16; |
|
517 |
|
518 /** |
|
519 Function to write the subtree below aPtr and return the head |
|
520 */ |
|
521 TUint32* HuffmanSubTree(TUint32* aPtr,const TUint32* aValue,TUint32** aLevel) |
|
522 { |
|
523 TUint32* l=*aLevel++; |
|
524 if (l>aValue) |
|
525 { |
|
526 TUint32* sub0=HuffmanSubTree(aPtr,aValue,aLevel); // 0-tree first |
|
527 aPtr=HuffmanSubTree(sub0,aValue-(aPtr-sub0)-1,aLevel); // 1-tree |
|
528 TInt branch0=(TUint8*)sub0-(TUint8*)(aPtr-1); |
|
529 *--aPtr=KBranch1|branch0; |
|
530 } |
|
531 else if (l==aValue) |
|
532 { |
|
533 TUint term0=*aValue--; // 0-term |
|
534 aPtr=HuffmanSubTree(aPtr,aValue,aLevel); // 1-tree |
|
535 *--aPtr=KBranch1|(term0>>16); |
|
536 } |
|
537 else // l<iNext |
|
538 { |
|
539 TUint term0=*aValue--; // 0-term |
|
540 TUint term1=*aValue--; |
|
541 *--aPtr=(term1>>16<<16)|(term0>>16); |
|
542 } |
|
543 return aPtr; |
|
544 } |
|
545 |
|
546 /** |
|
547 Create a canonical Huffman decoding tree |
|
548 |
|
549 This generates the huffman decoding tree used by TBitInput::HuffmanL() to read huffman |
|
550 encoded data. The input is table of code lengths, as generated by Huffman::HuffmanL() |
|
551 and must represent a valid huffman code. |
|
552 |
|
553 @param "const TUint32 aHuffman[]" The table of code lengths as generated by Huffman::HuffmanL() |
|
554 @param "TInt aNumCodes" The number of codes in the table |
|
555 @param "TUint32 aDecodeTree[]" The space for the decoding tree. This must be the same |
|
556 size as the code-length table, and can safely be the same memory |
|
557 @param "TInt aSymbolBase" the base value for the output 'symbols' from the decoding tree, by default |
|
558 this is zero. |
|
559 |
|
560 @panic "USER ???" If the provided code is not a valid Huffman coding |
|
561 |
|
562 @see IsValid() |
|
563 @see HuffmanL() |
|
564 */ |
|
565 void Huffman::Decoding(const TUint32 aHuffman[],TInt aNumCodes,TUint32 aDecodeTree[],TInt aSymbolBase) |
|
566 { |
|
567 if(!IsValid(aHuffman,aNumCodes)) |
|
568 throw E32ImageCompressionError(HUFFMANINVALIDCODINGERROR); |
|
569 |
|
570 TFixedArray<TInt,KMaxCodeLength> counts; |
|
571 counts.Reset(); |
|
572 TInt codes=0; |
|
573 TInt ii; |
|
574 for (ii=0;ii<aNumCodes;++ii) |
|
575 { |
|
576 TInt len=aHuffman[ii]; |
|
577 aDecodeTree[ii]=len; |
|
578 if (--len>=0) |
|
579 { |
|
580 ++counts[len]; |
|
581 ++codes; |
|
582 } |
|
583 } |
|
584 |
|
585 TFixedArray<TUint32*,KMaxCodeLength> level; |
|
586 TUint32* lit=aDecodeTree+codes; |
|
587 for (ii=0;ii<KMaxCodeLength;++ii) |
|
588 { |
|
589 level[ii]=lit; |
|
590 lit-=counts[ii]; |
|
591 } |
|
592 |
|
593 aSymbolBase=(aSymbolBase<<17)+(KHuffTerminate<<16); |
|
594 for (ii=0;ii<aNumCodes;++ii) |
|
595 { |
|
596 TUint len=TUint8(aDecodeTree[ii]); |
|
597 if (len) |
|
598 *--level[len-1]|=(ii<<17)+aSymbolBase; |
|
599 } |
|
600 |
|
601 if (codes==1) // codes==1 special case: tree isn't complete |
|
602 { |
|
603 TUint term=aDecodeTree[0]>>16; |
|
604 aDecodeTree[0]=term|(term<<16); // 0- and 1-terminate at root |
|
605 } |
|
606 else if (codes>1) |
|
607 HuffmanSubTree(aDecodeTree+codes-1,aDecodeTree+codes-1,&level[0]); |
|
608 } |
|
609 |
|
610 /** |
|
611 The decoding tree for the externalised code |
|
612 */ |
|
613 const TUint32 HuffmanDecoding[]= |
|
614 { |
|
615 0x0004006c, |
|
616 0x00040064, |
|
617 0x0004005c, |
|
618 0x00040050, |
|
619 0x00040044, |
|
620 0x0004003c, |
|
621 0x00040034, |
|
622 0x00040021, |
|
623 0x00040023, |
|
624 0x00040025, |
|
625 0x00040027, |
|
626 0x00040029, |
|
627 0x00040014, |
|
628 0x0004000c, |
|
629 0x00040035, |
|
630 0x00390037, |
|
631 0x00330031, |
|
632 0x0004002b, |
|
633 0x002f002d, |
|
634 0x001f001d, |
|
635 0x001b0019, |
|
636 0x00040013, |
|
637 0x00170015, |
|
638 0x0004000d, |
|
639 0x0011000f, |
|
640 0x000b0009, |
|
641 0x00070003, |
|
642 0x00050001 |
|
643 }; |
|
644 |
|
645 |
|
646 /** |
|
647 Restore a canonical huffman encoding from a bit stream |
|
648 |
|
649 The encoding must have been stored using Huffman::ExternalizeL(). The resulting |
|
650 code-length table can be used to create an encoding table using Huffman::Encoding() |
|
651 or a decoding tree using Huffman::Decoding(). |
|
652 |
|
653 @param "TBitInput& aInput" The input stream with the encoding |
|
654 @param "TUint32 aHuffman[]" The internalized code-length table is placed here |
|
655 @param "TInt aNumCodes" The number of huffman codes in the table |
|
656 |
|
657 @leave "TBitInput::HuffmanL()" |
|
658 |
|
659 @see ExternalizeL() |
|
660 See ExternalizeL for a description of the format |
|
661 */ |
|
662 void Huffman::InternalizeL(TBitInput& aInput,TUint32 aHuffman[],TInt aNumCodes) |
|
663 { |
|
664 // initialise move-to-front list |
|
665 TFixedArray<TUint8,Huffman::KMetaCodes> list; |
|
666 for (TInt i=0;i<list.Count();++i) |
|
667 list[i]=TUint8(i); |
|
668 |
|
669 TInt last=0; |
|
670 // extract codes, reverse rle-0 and mtf encoding in one pass |
|
671 TUint32* p=aHuffman; |
|
672 const TUint32* end=aHuffman+aNumCodes; |
|
673 TInt rl=0; |
|
674 while (p+rl<end) |
|
675 { |
|
676 TInt c=aInput.HuffmanL(HuffmanDecoding); |
|
677 if (c<2) |
|
678 { |
|
679 // one of the zero codes used by RLE-0 |
|
680 // update he run-length |
|
681 rl+=rl+c+1; |
|
682 } |
|
683 else |
|
684 { |
|
685 while (rl>0) |
|
686 { |
|
687 if (p>end) |
|
688 { |
|
689 throw E32ImageCompressionError(HUFFMANINVALIDCODINGERROR); |
|
690 } |
|
691 *p++=last; |
|
692 --rl; |
|
693 } |
|
694 --c; |
|
695 list[0]=TUint8(last); |
|
696 last=list[c]; |
|
697 |
|
698 memmove((void * const)&list[1],(const void * const)&list[0],(size_t)c); |
|
699 if (p>end) |
|
700 { |
|
701 throw E32ImageCompressionError(HUFFMANINVALIDCODINGERROR); |
|
702 } |
|
703 *p++=last; |
|
704 } |
|
705 } |
|
706 while (rl>0) |
|
707 { |
|
708 if (p>end) |
|
709 { |
|
710 throw E32ImageCompressionError(HUFFMANINVALIDCODINGERROR); |
|
711 } |
|
712 *p++=last; |
|
713 --rl; |
|
714 } |
|
715 } |
|
716 |
|
717 /** |
|
718 bit-stream input class |
|
719 Reverse the byte-order of a 32 bit value |
|
720 This generates optimal ARM code (4 instructions) |
|
721 */ |
|
722 inline TUint reverse(TUint aVal) |
|
723 { |
|
724 TUint v=(aVal<<16)|(aVal>>16); |
|
725 v^=aVal; |
|
726 v&=0xff00ffff; |
|
727 aVal=(aVal>>8)|(aVal<<24); |
|
728 return aVal^(v>>8); |
|
729 } |
|
730 |
|
731 /** |
|
732 Construct a bit stream input object |
|
733 |
|
734 Following construction the bit stream is ready for reading bits, but will |
|
735 immediately call UnderflowL() as the input buffer is empty. |
|
736 */ |
|
737 TBitInput::TBitInput():iCount(0),iRemain(0) |
|
738 { |
|
739 |
|
740 } |
|
741 |
|
742 /** |
|
743 Construct a bit stream input object over a buffer |
|
744 |
|
745 Following construction the bit stream is ready for reading bits from the specified buffer. |
|
746 |
|
747 @param "const TUint8* aPtr" The address of the buffer containing the bit stream |
|
748 @param "TInt aLength" The length of the bitstream in bits |
|
749 @param "TInt aOffset" The bit offset from the start of the buffer to the bit stream (defaults to zero) |
|
750 */ |
|
751 TBitInput::TBitInput(const TUint8* aPtr, TInt aLength, TInt aOffset) |
|
752 { |
|
753 Set(aPtr,aLength,aOffset); |
|
754 } |
|
755 |
|
756 /** |
|
757 Set the memory buffer to use for input. |
|
758 |
|
759 Bits will be read from this buffer until it is empty, at which point UnderflowL() will be called. |
|
760 |
|
761 @param "const TUint8* aPtr" The address of the buffer containing the bit stream |
|
762 @param "TInt aLength" The length of the bitstream in bits |
|
763 @param "TInt aOffset" The bit offset from the start of the buffer to the bit stream (defaults to zero) |
|
764 */ |
|
765 void TBitInput::Set(const TUint8* aPtr, TInt aLength, TInt aOffset) |
|
766 { |
|
767 TUint p=(TUint)aPtr; |
|
768 p+=aOffset>>3; // nearest byte to the specified bit offset |
|
769 aOffset&=7; // bit offset within the byte |
|
770 const TUint32* ptr=(const TUint32*)(p&~3); // word containing this byte |
|
771 aOffset+=(p&3)<<3; // bit offset within the word |
|
772 if (aLength==0) |
|
773 iCount=0; |
|
774 else |
|
775 { |
|
776 // read the first few bits of the stream |
|
777 iBits=reverse(*ptr++)<<aOffset; |
|
778 aOffset=32-aOffset; |
|
779 aLength-=aOffset; |
|
780 if (aLength<0) |
|
781 aOffset+=aLength; |
|
782 iCount=aOffset; |
|
783 } |
|
784 iRemain=aLength; |
|
785 iPtr=ptr; |
|
786 } |
|
787 |
|
788 #ifndef __HUFFMAN_MACHINE_CODED__ |
|
789 |
|
790 /** |
|
791 Read a single bit from the input |
|
792 |
|
793 Return the next bit in the input stream. This will call UnderflowL() if there are no more |
|
794 bits available. |
|
795 |
|
796 @return The next bit in the stream |
|
797 |
|
798 @leave "UnderflowL()" It the bit stream is exhausted more UnderflowL is called to get more |
|
799 data |
|
800 */ |
|
801 TUint TBitInput::ReadL() |
|
802 { |
|
803 TInt c=iCount; |
|
804 TUint bits=iBits; |
|
805 if (--c<0) |
|
806 return ReadL(1); |
|
807 iCount=c; |
|
808 iBits=bits<<1; |
|
809 return bits>>31; |
|
810 } |
|
811 |
|
812 /** |
|
813 Read a multi-bit value from the input |
|
814 |
|
815 Return the next few bits as an unsigned integer. The last bit read is the least significant |
|
816 bit of the returned value, and the value is zero extended to return a 32-bit result. |
|
817 |
|
818 A read of zero bits will always reaturn zero. |
|
819 |
|
820 This will call UnderflowL() if there are not enough bits available. |
|
821 |
|
822 @param "TInt aSize" The number of bits to read |
|
823 |
|
824 @return The bits read from the stream |
|
825 |
|
826 @leave "UnderflowL()" It the bit stream is exhausted more UnderflowL is called to get more |
|
827 data |
|
828 */ |
|
829 TUint TBitInput::ReadL(TInt aSize) |
|
830 { |
|
831 if (!aSize) |
|
832 return 0; |
|
833 TUint val=0; |
|
834 TUint bits=iBits; |
|
835 iCount-=aSize; |
|
836 while (iCount<0) |
|
837 { |
|
838 // need more bits |
|
839 #ifdef __CPU_X86 |
|
840 // X86 does not allow shift-by-32 |
|
841 if (iCount+aSize!=0) |
|
842 val|=bits>>(32-(iCount+aSize))<<(-iCount); // scrub low order bits |
|
843 #else |
|
844 val|=bits>>(32-(iCount+aSize))<<(-iCount); // scrub low order bits |
|
845 #endif |
|
846 aSize=-iCount; // bits still required |
|
847 if (iRemain>0) |
|
848 { |
|
849 bits=reverse(*iPtr++); |
|
850 iCount+=32; |
|
851 iRemain-=32; |
|
852 if (iRemain<0) |
|
853 iCount+=iRemain; |
|
854 } |
|
855 else |
|
856 { |
|
857 UnderflowL(); |
|
858 bits=iBits; |
|
859 iCount-=aSize; |
|
860 } |
|
861 } |
|
862 |
|
863 #ifdef __CPU_X86 |
|
864 // X86 does not allow shift-by-32 |
|
865 iBits=aSize==32?0:bits<<aSize; |
|
866 #else |
|
867 iBits=bits<<aSize; |
|
868 #endif |
|
869 |
|
870 return val|(bits>>(32-aSize)); |
|
871 } |
|
872 |
|
873 /** |
|
874 Read and decode a Huffman Code |
|
875 |
|
876 Interpret the next bits in the input as a Huffman code in the specified decoding. |
|
877 The decoding tree should be the output from Huffman::Decoding(). |
|
878 |
|
879 @param "const TUint32* aTree" The huffman decoding tree |
|
880 |
|
881 @return The symbol that was decoded |
|
882 |
|
883 @leave "UnderflowL()" It the bit stream is exhausted more UnderflowL is called to get more |
|
884 data |
|
885 */ |
|
886 TUint TBitInput::HuffmanL(const TUint32* aTree) |
|
887 { |
|
888 TUint huff=0; |
|
889 do |
|
890 { |
|
891 aTree=(const TUint32*)(((TUint8*)aTree)+(huff>>16)); |
|
892 huff=*aTree; |
|
893 if (ReadL()==0) |
|
894 huff<<=16; |
|
895 } while ((huff&0x10000u)==0); |
|
896 |
|
897 return huff>>17; |
|
898 } |
|
899 |
|
900 #endif |
|
901 |
|
902 /** |
|
903 Handle an empty input buffer |
|
904 |
|
905 This virtual function is called when the input buffer is empty and more bits are required. |
|
906 It should reset the input buffer with more data using Set(). |
|
907 |
|
908 A derived class can replace this to read the data from a file (for example) before reseting |
|
909 the input buffer. |
|
910 |
|
911 @leave "KErrUnderflow" The default implementation leaves |
|
912 */ |
|
913 void TBitInput::UnderflowL() |
|
914 { |
|
915 throw E32ImageCompressionError(HUFFMANBUFFEROVERFLOWERROR); |
|
916 } |
|
917 |