|
1 /* |
|
2 * Copyright (c) 2009 Nokia Corporation and/or its subsidiary(-ies). |
|
3 * All rights reserved. |
|
4 * This component and the accompanying materials are made available |
|
5 * under the terms of "Eclipse Public License v1.0" |
|
6 * which accompanies this distribution, and is available |
|
7 * at the URL "http://www.eclipse.org/legal/epl-v10.html". |
|
8 * |
|
9 * Initial Contributors: |
|
10 * Nokia Corporation - initial contribution. |
|
11 * |
|
12 * Contributors: |
|
13 * |
|
14 * Description: |
|
15 * |
|
16 */ |
|
17 |
|
18 #ifdef _MSC_VER |
|
19 #pragma warning(disable: 4710) // function not inlined |
|
20 #endif |
|
21 |
|
22 #include <cassert> |
|
23 #include "huffman.h" |
|
24 //#include "errorhandler.h" |
|
25 #include "farray.h" |
|
26 |
|
27 |
|
28 |
|
29 /** |
|
30 Recursive function to calculate the code lengths from the node tree |
|
31 @internalComponent |
|
32 @released |
|
33 */ |
|
34 void HuffmanLengthsL(TUint32* aLengths,const TNode* aNodes,TInt aNode,TInt aLen) |
|
35 { |
|
36 if (++aLen>Huffman::KMaxCodeLength) |
|
37 throw E32ImageCompressionError(E32ImageCompressionError::HUFFMANBUFFEROVERFLOWERROR); |
|
38 |
|
39 const TNode& node=aNodes[aNode]; |
|
40 TUint x=node.iLeft; |
|
41 if (x&KLeaf) |
|
42 aLengths[x&~KLeaf]=aLen; |
|
43 else |
|
44 HuffmanLengthsL(aLengths,aNodes,x,aLen); |
|
45 x=node.iRight; |
|
46 if (x&KLeaf) |
|
47 aLengths[x&~KLeaf]=aLen; |
|
48 else |
|
49 HuffmanLengthsL(aLengths,aNodes,x,aLen); |
|
50 } |
|
51 |
|
52 /** |
|
53 Function to Insert the {aCount,aValue} pair into the already sorted array of nodes |
|
54 @internalComponent |
|
55 @released |
|
56 */ |
|
57 void InsertInOrder(TNode* aNodes, TInt aSize, TUint aCount, TInt aVal) |
|
58 { |
|
59 // Uses Insertion sort following a binary search... |
|
60 TInt l=0, r=aSize; |
|
61 while (l < r) |
|
62 { |
|
63 TInt m = (l+r) >> 1; |
|
64 if (aNodes[m].iCount<aCount) |
|
65 r=m; |
|
66 else |
|
67 l=m+1; |
|
68 } |
|
69 memmove(aNodes+l+1,aNodes+l,sizeof(TNode)*(aSize-l)); |
|
70 aNodes[l].iCount=aCount; |
|
71 aNodes[l].iRight=TUint16(aVal); |
|
72 } |
|
73 |
|
74 /** |
|
75 Generate a Huffman code. |
|
76 |
|
77 This generates a Huffman code for a given set of code frequencies. The output is a table of |
|
78 code lengths which can be used to build canonincal encoding tables or decoding trees for use |
|
79 with the TBitInput and TBitOutput classes. |
|
80 |
|
81 Entries in the table with a frequency of zero will have a zero code length and thus no |
|
82 associated huffman encoding. If each such symbol should have a maximum length encoding, they |
|
83 must be given at least a frequency of 1. |
|
84 |
|
85 For an alphabet of n symbols, this algorithm has a transient memory overhead of 8n, and a |
|
86 time complexity of O(n*log(n)). |
|
87 |
|
88 @param "const TUint32 aFrequency[]" The table of code frequencies |
|
89 @param "TInt aNumCodes" The number of codes in the table |
|
90 @param "TUint32 aHuffman[]" The table for the output code-length table. This must be the same |
|
91 size as the frequency table, and can safely be the same table |
|
92 |
|
93 @leave "KErrNoMemory" If memory used for code generation cannot be allocated |
|
94 @panic "USER ???" If the number of codes exceeds Huffman::KMaxCodes |
|
95 */ |
|
96 void Huffman::HuffmanL(const TUint32 aFrequency[],TInt aNumCodes,TUint32 aHuffman[]) |
|
97 { |
|
98 if(TUint(aNumCodes)>TUint(KMaxCodes)) |
|
99 throw E32ImageCompressionError(E32ImageCompressionError::HUFFMANTOOMANYCODESERROR); |
|
100 |
|
101 // Sort the values into decreasing order of frequency |
|
102 TNode* nodes = new TNode[aNumCodes]; |
|
103 |
|
104 TInt lCount=0; |
|
105 |
|
106 for (TInt ii=0;ii<aNumCodes;++ii) |
|
107 { |
|
108 TInt c=aFrequency[ii]; |
|
109 if (c!=0) |
|
110 InsertInOrder(nodes,lCount++,c,ii|KLeaf); |
|
111 } |
|
112 |
|
113 // default code length is zero |
|
114 memset(aHuffman,0,aNumCodes*sizeof(TUint32)); |
|
115 |
|
116 if (lCount==0) |
|
117 { |
|
118 // no codes with frequency>0. No code has a length |
|
119 } |
|
120 else if (lCount==1) |
|
121 { |
|
122 // special case for a single value (always encode as "0") |
|
123 aHuffman[nodes[0].iRight&~KLeaf]=1; |
|
124 } |
|
125 else |
|
126 { |
|
127 // Huffman algorithm: pair off least frequent nodes and reorder |
|
128 do |
|
129 { |
|
130 --lCount; |
|
131 TUint c=nodes[lCount].iCount + nodes[lCount-1].iCount; |
|
132 nodes[lCount].iLeft=nodes[lCount-1].iRight; |
|
133 // re-order the leaves now to reflect new combined frequency 'c' |
|
134 InsertInOrder(nodes,lCount-1,c,lCount); |
|
135 } while (lCount>1); |
|
136 // generate code lengths in aHuffman[] |
|
137 HuffmanLengthsL(aHuffman,nodes,1,0); |
|
138 } |
|
139 |
|
140 delete [] nodes; |
|
141 |
|
142 if(!IsValid(aHuffman,aNumCodes)) |
|
143 throw E32ImageCompressionError(E32ImageCompressionError::HUFFMANINVALIDCODINGERROR); |
|
144 } |
|
145 |
|
146 /** |
|
147 Validate a Huffman encoding |
|
148 |
|
149 This verifies that a Huffman coding described by the code lengths is valid. In particular, |
|
150 it ensures that no code exceeds the maximum length and that it is possible to generate a |
|
151 canonical coding for the specified lengths. |
|
152 |
|
153 @param "const TUint32 aHuffman[]" The table of code lengths as generated by Huffman::HuffmanL() |
|
154 @param "TInt aNumCodes" The number of codes in the table |
|
155 |
|
156 @return True if the code is valid, otherwise false |
|
157 */ |
|
158 TBool Huffman::IsValid(const TUint32 aHuffman[],TInt aNumCodes) |
|
159 { |
|
160 // The code is valid if one of the following holds: |
|
161 // (a) the code exactly fills the 'code space' |
|
162 // (b) there is only a single symbol with code length 1 |
|
163 // (c) there are no encoded symbols |
|
164 // |
|
165 TUint remain=1<<KMaxCodeLength; |
|
166 TInt totlen=0; |
|
167 for (const TUint32* p=aHuffman+aNumCodes; p>aHuffman;) |
|
168 { |
|
169 TInt len=*--p; |
|
170 if (len>0) |
|
171 { |
|
172 totlen+=len; |
|
173 if (len>KMaxCodeLength) |
|
174 return 0; |
|
175 |
|
176 TUint c=1<<(KMaxCodeLength-len); |
|
177 if (c>remain) |
|
178 return 0; |
|
179 |
|
180 remain-=c; |
|
181 } |
|
182 } |
|
183 |
|
184 return remain==0 || totlen<=1; |
|
185 } |
|
186 |
|
187 /** |
|
188 Create a canonical Huffman encoding table |
|
189 |
|
190 This generates the huffman codes used by TBitOutput::HuffmanL() to write huffman encoded data. |
|
191 The input is table of code lengths, as generated by Huffman::HuffmanL() and must represent a |
|
192 valid huffman code. |
|
193 |
|
194 @param "const TUint32 aHuffman[]" The table of code lengths as generated by Huffman::HuffmanL() |
|
195 @param "TInt aNumCodes" The number of codes in the table |
|
196 @param "TUint32 aEncodeTable[]" The table for the output huffman codes. This must be the same |
|
197 size as the code-length table, and can safely be the same table. |
|
198 |
|
199 @panic "USER ???" If the provided code is not a valid Huffman coding |
|
200 |
|
201 @see IsValid() |
|
202 @see HuffmanL() |
|
203 */ |
|
204 void Huffman::Encoding(const TUint32 aHuffman[],TInt aNumCodes,TUint32 aEncodeTable[]) |
|
205 { |
|
206 if (!IsValid(aHuffman,aNumCodes)) |
|
207 throw E32ImageCompressionError(E32ImageCompressionError::HUFFMANINVALIDCODINGERROR); |
|
208 |
|
209 TFixedArray<TInt,KMaxCodeLength> lenCount; |
|
210 lenCount.Reset(); |
|
211 |
|
212 TInt ii; |
|
213 for (ii=0;ii<aNumCodes;++ii) |
|
214 { |
|
215 TInt len=aHuffman[ii]-1; |
|
216 if (len>=0) |
|
217 ++lenCount[len]; |
|
218 } |
|
219 |
|
220 TFixedArray<TUint,KMaxCodeLength> nextCode; |
|
221 TUint code=0; |
|
222 for (ii=0;ii<KMaxCodeLength;++ii) |
|
223 { |
|
224 code<<=1; |
|
225 nextCode[ii]=code; |
|
226 code+=lenCount[ii]; |
|
227 } |
|
228 |
|
229 for (ii=0;ii<aNumCodes;++ii) |
|
230 { |
|
231 TInt len=aHuffman[ii]; |
|
232 if (len==0) |
|
233 aEncodeTable[ii]=0; |
|
234 else |
|
235 { |
|
236 aEncodeTable[ii] = (nextCode[len-1]<<(KMaxCodeLength-len))|(len<<KMaxCodeLength); |
|
237 ++nextCode[len-1]; |
|
238 } |
|
239 } |
|
240 } |
|
241 |
|
242 /** |
|
243 The encoding table for the externalised code |
|
244 @internalComponent |
|
245 @released |
|
246 */ |
|
247 const TUint32 HuffmanEncoding[]= |
|
248 { |
|
249 0x10000000, |
|
250 0x1c000000, |
|
251 0x12000000, |
|
252 0x1d000000, |
|
253 0x26000000, |
|
254 0x26800000, |
|
255 0x2f000000, |
|
256 0x37400000, |
|
257 0x37600000, |
|
258 0x37800000, |
|
259 0x3fa00000, |
|
260 0x3fb00000, |
|
261 0x3fc00000, |
|
262 0x3fd00000, |
|
263 0x47e00000, |
|
264 0x47e80000, |
|
265 0x47f00000, |
|
266 0x4ff80000, |
|
267 0x57fc0000, |
|
268 0x5ffe0000, |
|
269 0x67ff0000, |
|
270 0x77ff8000, |
|
271 0x7fffa000, |
|
272 0x7fffb000, |
|
273 0x7fffc000, |
|
274 0x7fffd000, |
|
275 0x7fffe000, |
|
276 0x87fff000, |
|
277 0x87fff800 |
|
278 }; |
|
279 |
|
280 |
|
281 const TInt KHuffTerminate=0x0001; |
|
282 const TUint32 KBranch1=sizeof(TUint32)<<16; |
|
283 |
|
284 /** |
|
285 Function to write the subtree below aPtr and return the head |
|
286 */ |
|
287 TUint32* HuffmanSubTree(TUint32* aPtr,const TUint32* aValue,TUint32** aLevel) |
|
288 { |
|
289 TUint32* l=*aLevel++; |
|
290 if (l>aValue) |
|
291 { |
|
292 TUint32* sub0=HuffmanSubTree(aPtr,aValue,aLevel); // 0-tree first |
|
293 aPtr=HuffmanSubTree(sub0,aValue-(aPtr-sub0)-1,aLevel); // 1-tree |
|
294 TInt branch0=(TUint8*)sub0-(TUint8*)(aPtr-1); |
|
295 *--aPtr=KBranch1|branch0; |
|
296 } |
|
297 else if (l==aValue) |
|
298 { |
|
299 TUint term0=*aValue--; // 0-term |
|
300 aPtr=HuffmanSubTree(aPtr,aValue,aLevel); // 1-tree |
|
301 *--aPtr=KBranch1|(term0>>16); |
|
302 } |
|
303 else // l<iNext |
|
304 { |
|
305 TUint term0=*aValue--; // 0-term |
|
306 TUint term1=*aValue--; |
|
307 *--aPtr=(term1>>16<<16)|(term0>>16); |
|
308 } |
|
309 return aPtr; |
|
310 } |
|
311 |
|
312 /** |
|
313 Create a canonical Huffman decoding tree |
|
314 |
|
315 This generates the huffman decoding tree used by TBitInput::HuffmanL() to read huffman |
|
316 encoded data. The input is table of code lengths, as generated by Huffman::HuffmanL() |
|
317 and must represent a valid huffman code. |
|
318 |
|
319 @param "const TUint32 aHuffman[]" The table of code lengths as generated by Huffman::HuffmanL() |
|
320 @param "TInt aNumCodes" The number of codes in the table |
|
321 @param "TUint32 aDecodeTree[]" The space for the decoding tree. This must be the same |
|
322 size as the code-length table, and can safely be the same memory |
|
323 @param "TInt aSymbolBase" the base value for the output 'symbols' from the decoding tree, by default |
|
324 this is zero. |
|
325 |
|
326 @panic "USER ???" If the provided code is not a valid Huffman coding |
|
327 |
|
328 @see IsValid() |
|
329 @see HuffmanL() |
|
330 */ |
|
331 void Huffman::Decoding(const TUint32 aHuffman[],TInt aNumCodes,TUint32 aDecodeTree[],TInt aSymbolBase) |
|
332 { |
|
333 if(!IsValid(aHuffman,aNumCodes)) |
|
334 throw E32ImageCompressionError(E32ImageCompressionError::HUFFMANINVALIDCODINGERROR); |
|
335 |
|
336 TFixedArray<TInt,KMaxCodeLength> counts; |
|
337 counts.Reset(); |
|
338 TInt codes=0; |
|
339 TInt ii; |
|
340 for (ii=0;ii<aNumCodes;++ii) |
|
341 { |
|
342 TInt len=aHuffman[ii]; |
|
343 aDecodeTree[ii]=len; |
|
344 if (--len>=0) |
|
345 { |
|
346 ++counts[len]; |
|
347 ++codes; |
|
348 } |
|
349 } |
|
350 |
|
351 TFixedArray<TUint32*,KMaxCodeLength> level; |
|
352 TUint32* lit=aDecodeTree+codes; |
|
353 for (ii=0;ii<KMaxCodeLength;++ii) |
|
354 { |
|
355 level[ii]=lit; |
|
356 lit-=counts[ii]; |
|
357 } |
|
358 |
|
359 aSymbolBase=(aSymbolBase<<17)+(KHuffTerminate<<16); |
|
360 for (ii=0;ii<aNumCodes;++ii) |
|
361 { |
|
362 TUint len=TUint8(aDecodeTree[ii]); |
|
363 if (len) |
|
364 *--level[len-1]|=(ii<<17)+aSymbolBase; |
|
365 } |
|
366 |
|
367 if (codes==1) // codes==1 special case: incomplete tree |
|
368 { |
|
369 TUint term=aDecodeTree[0]>>16; |
|
370 aDecodeTree[0]=term|(term<<16); // 0- and 1-terminate at root |
|
371 } |
|
372 else if (codes>1) |
|
373 HuffmanSubTree(aDecodeTree+codes-1,aDecodeTree+codes-1,&level[0]); |
|
374 } |
|
375 |
|
376 /** |
|
377 The decoding tree for the externalised code |
|
378 */ |
|
379 const TUint32 HuffmanDecoding[]= |
|
380 { |
|
381 0x0004006c, |
|
382 0x00040064, |
|
383 0x0004005c, |
|
384 0x00040050, |
|
385 0x00040044, |
|
386 0x0004003c, |
|
387 0x00040034, |
|
388 0x00040021, |
|
389 0x00040023, |
|
390 0x00040025, |
|
391 0x00040027, |
|
392 0x00040029, |
|
393 0x00040014, |
|
394 0x0004000c, |
|
395 0x00040035, |
|
396 0x00390037, |
|
397 0x00330031, |
|
398 0x0004002b, |
|
399 0x002f002d, |
|
400 0x001f001d, |
|
401 0x001b0019, |
|
402 0x00040013, |
|
403 0x00170015, |
|
404 0x0004000d, |
|
405 0x0011000f, |
|
406 0x000b0009, |
|
407 0x00070003, |
|
408 0x00050001 |
|
409 }; |
|
410 |
|
411 |
|
412 /** |
|
413 Restore a canonical huffman encoding from a bit stream |
|
414 |
|
415 The encoding must have been stored using Huffman::ExternalizeL(). The resulting |
|
416 code-length table can be used to create an encoding table using Huffman::Encoding() |
|
417 or a decoding tree using Huffman::Decoding(). |
|
418 |
|
419 @param "TBitInput& aInput" The input stream with the encoding |
|
420 @param "TUint32 aHuffman[]" The internalized code-length table is placed here |
|
421 @param "TInt aNumCodes" The number of huffman codes in the table |
|
422 |
|
423 @leave "TBitInput::HuffmanL()" |
|
424 |
|
425 @see ExternalizeL() |
|
426 See ExternalizeL for a description of the format |
|
427 */ |
|
428 void Huffman::InternalizeL(TBitInput& aInput,TUint32 aHuffman[],TInt aNumCodes) |
|
429 { |
|
430 // initialise move-to-front list |
|
431 TFixedArray<TUint8,Huffman::KMetaCodes> list; |
|
432 for (TInt i=0;i<list.Count();++i) |
|
433 list[i]=TUint8(i); |
|
434 |
|
435 TInt last=0; |
|
436 // extract codes, reverse rle-0 and mtf encoding in one pass |
|
437 TUint32* p=aHuffman; |
|
438 const TUint32* end=aHuffman+aNumCodes; |
|
439 TInt rl=0; |
|
440 while (p+rl<end) |
|
441 { |
|
442 TInt c=aInput.HuffmanL(HuffmanDecoding); |
|
443 if (c<2) |
|
444 { |
|
445 // one of the zero codes used by RLE-0 |
|
446 // update he run-length |
|
447 rl+=rl+c+1; |
|
448 } |
|
449 else |
|
450 { |
|
451 while (rl>0) |
|
452 { |
|
453 if (p>end) |
|
454 { |
|
455 throw E32ImageCompressionError(E32ImageCompressionError::HUFFMANINVALIDCODINGERROR); |
|
456 } |
|
457 *p++=last; |
|
458 --rl; |
|
459 } |
|
460 --c; |
|
461 list[0]=TUint8(last); |
|
462 last=list[c]; |
|
463 |
|
464 memmove((void * const)&list[1],(const void * const)&list[0],(size_t)c); |
|
465 if (p>end) |
|
466 { |
|
467 throw E32ImageCompressionError(E32ImageCompressionError::HUFFMANINVALIDCODINGERROR); |
|
468 } |
|
469 *p++=last; |
|
470 } |
|
471 } |
|
472 while (rl>0) |
|
473 { |
|
474 if (p>end) |
|
475 { |
|
476 throw E32ImageCompressionError(E32ImageCompressionError::HUFFMANINVALIDCODINGERROR); |
|
477 } |
|
478 *p++=last; |
|
479 --rl; |
|
480 } |
|
481 } |
|
482 |
|
483 /** |
|
484 bit-stream input class |
|
485 Reverse the byte-order of a 32 bit value |
|
486 This generates optimal ARM code (4 instructions) |
|
487 */ |
|
488 inline TUint reverse(TUint aVal) |
|
489 { |
|
490 TUint v=(aVal<<16)|(aVal>>16); |
|
491 v^=aVal; |
|
492 v&=0xff00ffff; |
|
493 aVal=(aVal>>8)|(aVal<<24); |
|
494 return aVal^(v>>8); |
|
495 } |
|
496 |
|
497 /** |
|
498 Construct a bit stream input object |
|
499 |
|
500 Following construction the bit stream is ready for reading bits, but will |
|
501 immediately call UnderflowL() as the input buffer is empty. |
|
502 */ |
|
503 TBitInput::TBitInput():iCount(0),iRemain(0) |
|
504 { |
|
505 |
|
506 } |
|
507 |
|
508 /** |
|
509 Construct a bit stream input object over a buffer |
|
510 |
|
511 Following construction the bit stream is ready for reading bits from the specified buffer. |
|
512 |
|
513 @param "const TUint8* aPtr" The address of the buffer containing the bit stream |
|
514 @param "TInt aLength" The length of the bitstream in bits |
|
515 @param "TInt aOffset" The bit offset from the start of the buffer to the bit stream (defaults to zero) |
|
516 */ |
|
517 TBitInput::TBitInput(const TUint8* aPtr, TInt aLength, TInt aOffset) |
|
518 { |
|
519 Set(aPtr,aLength,aOffset); |
|
520 } |
|
521 |
|
522 /** |
|
523 Set the memory buffer to use for input. |
|
524 |
|
525 Bits will be read from this buffer until it is empty, at which point UnderflowL() will be called. |
|
526 |
|
527 @param "const TUint8* aPtr" The address of the buffer containing the bit stream |
|
528 @param "TInt aLength" The length of the bitstream in bits |
|
529 @param "TInt aOffset" The bit offset from the start of the buffer to the bit stream (defaults to zero) |
|
530 */ |
|
531 void TBitInput::Set(const TUint8* aPtr, TInt aLength, TInt aOffset) |
|
532 { |
|
533 TUint p=(TUint)aPtr; |
|
534 p+=aOffset>>3; // nearest byte to the specified bit offset |
|
535 aOffset&=7; // bit offset within the byte |
|
536 const TUint32* ptr=(const TUint32*)(p&~3); // word containing this byte |
|
537 aOffset+=(p&3)<<3; // bit offset within the word |
|
538 if (aLength==0) |
|
539 iCount=0; |
|
540 else |
|
541 { |
|
542 // read the first few bits of the stream |
|
543 iBits=reverse(*ptr++)<<aOffset; |
|
544 aOffset=32-aOffset; |
|
545 aLength-=aOffset; |
|
546 if (aLength<0) |
|
547 aOffset+=aLength; |
|
548 iCount=aOffset; |
|
549 } |
|
550 iRemain=aLength; |
|
551 iPtr=ptr; |
|
552 } |
|
553 |
|
554 #ifndef __HUFFMAN_MACHINE_CODED__ |
|
555 |
|
556 /** |
|
557 Read a single bit from the input |
|
558 |
|
559 Return the next bit in the input stream. This will call UnderflowL() if there are no more |
|
560 bits available. |
|
561 |
|
562 @return The next bit in the stream |
|
563 |
|
564 @leave "UnderflowL()" It the bit stream is exhausted more UnderflowL is called to get more |
|
565 data |
|
566 */ |
|
567 TUint TBitInput::ReadL() |
|
568 { |
|
569 TInt c=iCount; |
|
570 TUint bits=iBits; |
|
571 if (--c<0) |
|
572 return ReadL(1); |
|
573 iCount=c; |
|
574 iBits=bits<<1; |
|
575 return bits>>31; |
|
576 } |
|
577 |
|
578 /** |
|
579 Read a multi-bit value from the input |
|
580 |
|
581 Return the next few bits as an unsigned integer. The last bit read is the least significant |
|
582 bit of the returned value, and the value is zero extended to return a 32-bit result. |
|
583 |
|
584 A read of zero bits will always reaturn zero. |
|
585 |
|
586 This will call UnderflowL() if there are not enough bits available. |
|
587 |
|
588 @param "TInt aSize" The number of bits to read |
|
589 |
|
590 @return The bits read from the stream |
|
591 |
|
592 @leave "UnderflowL()" It the bit stream is exhausted more UnderflowL is called to get more |
|
593 data |
|
594 */ |
|
595 TUint TBitInput::ReadL(TInt aSize) |
|
596 { |
|
597 if (!aSize) |
|
598 return 0; |
|
599 TUint val=0; |
|
600 TUint bits=iBits; |
|
601 iCount-=aSize; |
|
602 while (iCount<0) |
|
603 { |
|
604 // need more bits |
|
605 #ifdef __CPU_X86 |
|
606 // X86 does not allow shift-by-32 |
|
607 if (iCount+aSize!=0) |
|
608 val|=bits>>(32-(iCount+aSize))<<(-iCount); // scrub low order bits |
|
609 #else |
|
610 val|=bits>>(32-(iCount+aSize))<<(-iCount); // scrub low order bits |
|
611 #endif |
|
612 aSize=-iCount; // bits still required |
|
613 if (iRemain>0) |
|
614 { |
|
615 bits=reverse(*iPtr++); |
|
616 iCount+=32; |
|
617 iRemain-=32; |
|
618 if (iRemain<0) |
|
619 iCount+=iRemain; |
|
620 } |
|
621 else |
|
622 { |
|
623 UnderflowL(); |
|
624 bits=iBits; |
|
625 iCount-=aSize; |
|
626 } |
|
627 } |
|
628 |
|
629 #ifdef __CPU_X86 |
|
630 // X86 does not allow shift-by-32 |
|
631 iBits=aSize==32?0:bits<<aSize; |
|
632 #else |
|
633 iBits=bits<<aSize; |
|
634 #endif |
|
635 |
|
636 return val|(bits>>(32-aSize)); |
|
637 } |
|
638 |
|
639 /** |
|
640 Read and decode a Huffman Code |
|
641 |
|
642 Interpret the next bits in the input as a Huffman code in the specified decoding. |
|
643 The decoding tree should be the output from Huffman::Decoding(). |
|
644 |
|
645 @param "const TUint32* aTree" The huffman decoding tree |
|
646 |
|
647 @return The symbol that was decoded |
|
648 |
|
649 @leave "UnderflowL()" It the bit stream is exhausted more UnderflowL is called to get more |
|
650 data |
|
651 */ |
|
652 TUint TBitInput::HuffmanL(const TUint32* aTree) |
|
653 { |
|
654 TUint huff=0; |
|
655 do |
|
656 { |
|
657 aTree=(const TUint32*)(((TUint8*)aTree)+(huff>>16)); |
|
658 huff=*aTree; |
|
659 if (ReadL()==0) |
|
660 huff<<=16; |
|
661 } while ((huff&0x10000u)==0); |
|
662 |
|
663 return huff>>17; |
|
664 } |
|
665 |
|
666 #endif |
|
667 |
|
668 /** |
|
669 Handle an empty input buffer |
|
670 |
|
671 This virtual function is called when the input buffer is empty and more bits are required. |
|
672 It should reset the input buffer with more data using Set(). |
|
673 |
|
674 A derived class can replace this to read the data from a file (for example) before reseting |
|
675 the input buffer. |
|
676 |
|
677 @leave "KErrUnderflow" The default implementation leaves |
|
678 */ |
|
679 void TBitInput::UnderflowL() |
|
680 { |
|
681 throw E32ImageCompressionError(E32ImageCompressionError::HUFFMANBUFFEROVERFLOWERROR); |
|
682 } |
|
683 |