1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/kernelhwsrv/kernel/eka/euser/us_decode.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,400 @@
1.4 +// Copyright (c) 1998-2009 Nokia Corporation and/or its subsidiary(-ies).
1.5 +// All rights reserved.
1.6 +// This component and the accompanying materials are made available
1.7 +// under the terms of the License "Eclipse Public License v1.0"
1.8 +// which accompanies this distribution, and is available
1.9 +// at the URL "http://www.eclipse.org/legal/epl-v10.html".
1.10 +//
1.11 +// Initial Contributors:
1.12 +// Nokia Corporation - initial contribution.
1.13 +//
1.14 +// Contributors:
1.15 +//
1.16 +// Description:
1.17 +// e32\euser\us_decode.cpp
1.18 +//
1.19 +//
1.20 +
1.21 +#include "e32huffman.h"
1.22 +#include <e32base.h>
1.23 +#include <e32base_private.h>
1.24 +#include <e32panic.h>
1.25 +#include <cpudefs.h>
1.26 +
1.27 +const TInt KHuffTerminate=0x0001;
1.28 +const TUint32 KBranch1=sizeof(TUint32)<<16;
1.29 +_LIT(KCat,"Huffman");
1.30 +
1.31 +TUint32* HuffmanSubTree(TUint32* aPtr,const TUint32* aValue,TUint32** aLevel)
1.32 +//
1.33 +// write the subtree below aPtr and return the head
1.34 +//
1.35 + {
1.36 + TUint32* l=*aLevel++;
1.37 + if (l>aValue)
1.38 + {
1.39 + TUint32* sub0=HuffmanSubTree(aPtr,aValue,aLevel); // 0-tree first
1.40 + aPtr=HuffmanSubTree(sub0,aValue-(aPtr-sub0)-1,aLevel); // 1-tree
1.41 + TInt branch0=(TUint8*)sub0-(TUint8*)(aPtr-1);
1.42 + *--aPtr=KBranch1|branch0;
1.43 + }
1.44 + else if (l==aValue)
1.45 + {
1.46 + TUint term0=*aValue--; // 0-term
1.47 + aPtr=HuffmanSubTree(aPtr,aValue,aLevel); // 1-tree
1.48 + *--aPtr=KBranch1|(term0>>16);
1.49 + }
1.50 + else // l<iNext
1.51 + {
1.52 + TUint term0=*aValue--; // 0-term
1.53 + TUint term1=*aValue--;
1.54 + *--aPtr=(term1>>16<<16)|(term0>>16);
1.55 + }
1.56 + return aPtr;
1.57 + }
1.58 +
1.59 +/** Create a canonical Huffman decoding tree
1.60 +
1.61 + This generates the huffman decoding tree used by TBitInput::HuffmanL() to read huffman
1.62 + encoded data. The input is table of code lengths, as generated by Huffman::HuffmanL()
1.63 + and must represent a valid huffman code.
1.64 +
1.65 + @param aHuffman The table of code lengths as generated by Huffman::HuffmanL()
1.66 + @param aNumCodes The number of codes in the table
1.67 + @param aDecodeTree The space for the decoding tree. This must be the same
1.68 + size as the code-length table, and can safely be the same memory
1.69 + @param aSymbolBase the base value for the output 'symbols' from the decoding tree, by default
1.70 + this is zero.
1.71 +
1.72 + @panic "USER ???" If the provided code is not a valid Huffman coding
1.73 +
1.74 + @see IsValid()
1.75 + @see HuffmanL()
1.76 +*/
1.77 +EXPORT_C void Huffman::Decoding(const TUint32 aHuffman[],TInt aNumCodes,TUint32 aDecodeTree[],TInt aSymbolBase)
1.78 + {
1.79 + __ASSERT_ALWAYS(IsValid(aHuffman,aNumCodes),User::Panic(KCat,EHuffmanInvalidCoding));
1.80 +//
1.81 + TFixedArray<TInt,KMaxCodeLength> counts;
1.82 + counts.Reset();
1.83 + TInt codes=0;
1.84 + TInt ii;
1.85 + for (ii=0;ii<aNumCodes;++ii)
1.86 + {
1.87 + TInt len=aHuffman[ii];
1.88 + aDecodeTree[ii]=len;
1.89 + if (--len>=0)
1.90 + {
1.91 + ++counts[len];
1.92 + ++codes;
1.93 + }
1.94 + }
1.95 +//
1.96 + TFixedArray<TUint32*,KMaxCodeLength> level;
1.97 + TUint32* lit=aDecodeTree+codes;
1.98 + for (ii=0;ii<KMaxCodeLength;++ii)
1.99 + {
1.100 + level[ii]=lit;
1.101 + lit-=counts[ii];
1.102 + }
1.103 + aSymbolBase=(aSymbolBase<<17)+(KHuffTerminate<<16);
1.104 + for (ii=0;ii<aNumCodes;++ii)
1.105 + {
1.106 + TUint len=TUint8(aDecodeTree[ii]);
1.107 + if (len)
1.108 + *--level[len-1]|=(ii<<17)+aSymbolBase;
1.109 + }
1.110 + if (codes==1) // codes==1 special case: incomplete tree
1.111 + {
1.112 + TUint term=aDecodeTree[0]>>16;
1.113 + aDecodeTree[0]=term|(term<<16); // 0- and 1-terminate at root
1.114 + }
1.115 + else if (codes>1)
1.116 + HuffmanSubTree(aDecodeTree+codes-1,aDecodeTree+codes-1,&level[0]);
1.117 + }
1.118 +
1.119 +// The decoding tree for the externalised code
1.120 +const TUint32 HuffmanDecoding[]=
1.121 + {
1.122 + 0x0004006c,
1.123 + 0x00040064,
1.124 + 0x0004005c,
1.125 + 0x00040050,
1.126 + 0x00040044,
1.127 + 0x0004003c,
1.128 + 0x00040034,
1.129 + 0x00040021,
1.130 + 0x00040023,
1.131 + 0x00040025,
1.132 + 0x00040027,
1.133 + 0x00040029,
1.134 + 0x00040014,
1.135 + 0x0004000c,
1.136 + 0x00040035,
1.137 + 0x00390037,
1.138 + 0x00330031,
1.139 + 0x0004002b,
1.140 + 0x002f002d,
1.141 + 0x001f001d,
1.142 + 0x001b0019,
1.143 + 0x00040013,
1.144 + 0x00170015,
1.145 + 0x0004000d,
1.146 + 0x0011000f,
1.147 + 0x000b0009,
1.148 + 0x00070003,
1.149 + 0x00050001
1.150 + };
1.151 +
1.152 +/** Restore a canonical huffman encoding from a bit stream
1.153 +
1.154 + The encoding must have been stored using Huffman::ExternalizeL(). The resulting
1.155 + code-length table can be used to create an encoding table using Huffman::Encoding()
1.156 + or a decoding tree using Huffman::Decoding().
1.157 +
1.158 + @param aInput The input stream with the encoding
1.159 + @param aHuffman The internalized code-length table is placed here
1.160 + @param aNumCodes The number of huffman codes in the table
1.161 +
1.162 + @leave TBitInput::HuffmanL()
1.163 +
1.164 + @see ExternalizeL()
1.165 +*/
1.166 +EXPORT_C void Huffman::InternalizeL(TBitInput& aInput,TUint32 aHuffman[],TInt aNumCodes)
1.167 +// See ExternalizeL for a description of the format
1.168 + {
1.169 + // initialise move-to-front list
1.170 + TFixedArray<TUint8,Huffman::KMetaCodes> list;
1.171 + for (TInt i=0;i<list.Count();++i)
1.172 + list[i]=TUint8(i);
1.173 + TInt last=0;
1.174 + // extract codes, reverse rle-0 and mtf encoding in one pass
1.175 + TUint32* p=aHuffman;
1.176 + const TUint32* end=aHuffman+aNumCodes;
1.177 + TUint rl=0;
1.178 + while (p+rl<end)
1.179 + {
1.180 + TInt c=aInput.HuffmanL(HuffmanDecoding);
1.181 + // c is now 0..28
1.182 + if (c<2)
1.183 + {
1.184 + // one of the zero codes used by RLE-0
1.185 + // update he run-length
1.186 + rl+=rl+c+1;
1.187 + }
1.188 + else
1.189 + {
1.190 + if(rl >= TUint(end-p))
1.191 + User::Leave(KErrCorrupt);
1.192 + while (rl>0)
1.193 + {
1.194 + *p++=last;
1.195 + --rl;
1.196 + }
1.197 + --c; // c is now 1..27
1.198 + list[0]=TUint8(last);
1.199 + last=list[c];
1.200 + Mem::Copy(&list[1],&list[0],c);
1.201 + *p++=last;
1.202 + }
1.203 + }
1.204 +
1.205 + while (p<end)
1.206 + *p++=last;
1.207 +
1.208 + }
1.209 +
1.210 +// bit-stream input class
1.211 +
1.212 +inline TUint reverse(TUint aVal)
1.213 +//
1.214 +// Reverse the byte-order of a 32 bit value
1.215 +// This generates optimal ARM code (4 instructions)
1.216 +//
1.217 + {
1.218 + TUint v=(aVal<<16)|(aVal>>16);
1.219 + v^=aVal;
1.220 + v&=0xff00ffff;
1.221 + aVal=(aVal>>8)|(aVal<<24);
1.222 + return aVal^(v>>8);
1.223 + }
1.224 +
1.225 +/** Construct a bit stream input object
1.226 +
1.227 + Following construction the bit stream is ready for reading bits, but will
1.228 + immediately call UnderflowL() as the input buffer is empty.
1.229 +*/
1.230 +EXPORT_C TBitInput::TBitInput()
1.231 + :iCount(0),iRemain(0)
1.232 + {}
1.233 +
1.234 +/** Construct a bit stream input object over a buffer
1.235 +
1.236 + Following construction the bit stream is ready for reading bits from
1.237 + the specified buffer.
1.238 +
1.239 + @param aPtr The address of the buffer containing the bit stream
1.240 + @param aLength The length of the bitstream in bits
1.241 + @param aOffset The bit offset from the start of the buffer to the bit stream (defaults to zero)
1.242 +*/
1.243 +EXPORT_C TBitInput::TBitInput(const TUint8* aPtr, TInt aLength, TInt aOffset)
1.244 + {
1.245 + Set(aPtr,aLength,aOffset);
1.246 + }
1.247 +
1.248 +/** Set the memory buffer to use for input
1.249 +
1.250 + Bits will be read from this buffer until it is empty, at which point
1.251 + UnderflowL() will be called.
1.252 +
1.253 + @param aPtr The address of the buffer containing the bit stream
1.254 + @param aLength The length of the bitstream in bits
1.255 + @param aOffset The bit offset from the start of the buffer to the bit stream (defaults to zero)
1.256 +*/
1.257 +EXPORT_C void TBitInput::Set(const TUint8* aPtr, TInt aLength, TInt aOffset)
1.258 + {
1.259 + TUint p=(TUint)aPtr;
1.260 + p+=aOffset>>3; // nearest byte to the specified bit offset
1.261 + aOffset&=7; // bit offset within the byte
1.262 + const TUint32* ptr=(const TUint32*)(p&~3); // word containing this byte
1.263 + aOffset+=(p&3)<<3; // bit offset within the word
1.264 + if (aLength==0)
1.265 + iCount=0;
1.266 + else
1.267 + {
1.268 + // read the first few bits of the stream
1.269 + iBits=reverse(*ptr++)<<aOffset;
1.270 + aOffset=32-aOffset;
1.271 + aLength-=aOffset;
1.272 + if (aLength<0)
1.273 + aOffset+=aLength;
1.274 + iCount=aOffset;
1.275 + }
1.276 + iRemain=aLength;
1.277 + iPtr=ptr;
1.278 + }
1.279 +
1.280 +#ifndef __HUFFMAN_MACHINE_CODED__
1.281 +
1.282 +/** Read a single bit from the input
1.283 +
1.284 + Return the next bit in the input stream. This will call UnderflowL() if
1.285 + there are no more bits available.
1.286 +
1.287 + @return The next bit in the stream
1.288 +
1.289 + @leave "UnderflowL()" It the bit stream is exhausted more UnderflowL is called
1.290 + to get more data
1.291 +*/
1.292 +EXPORT_C TUint TBitInput::ReadL()
1.293 + {
1.294 + TInt c=iCount;
1.295 + TUint bits=iBits;
1.296 + if (--c<0)
1.297 + return ReadL(1);
1.298 + iCount=c;
1.299 + iBits=bits<<1;
1.300 + return bits>>31;
1.301 + }
1.302 +
1.303 +/** Read a multi-bit value from the input
1.304 +
1.305 + Return the next few bits as an unsigned integer. The last bit read is
1.306 + the least significant bit of the returned value, and the value is
1.307 + zero extended to return a 32-bit result.
1.308 +
1.309 + A read of zero bits will always reaturn zero.
1.310 +
1.311 + This will call UnderflowL() if there are not enough bits available.
1.312 +
1.313 + @param aSize The number of bits to read
1.314 +
1.315 + @return The bits read from the stream
1.316 +
1.317 + @leave "UnderflowL()" It the bit stream is exhausted more UnderflowL is called
1.318 + to get more data
1.319 +*/
1.320 +EXPORT_C TUint TBitInput::ReadL(TInt aSize)
1.321 + {
1.322 + if (!aSize)
1.323 + return 0;
1.324 + TUint val=0;
1.325 + TUint bits=iBits;
1.326 + iCount-=aSize;
1.327 + while (iCount<0)
1.328 + {
1.329 + // need more bits
1.330 +#ifdef __CPU_X86
1.331 + // X86 does not allow shift-by-32
1.332 + if (iCount+aSize!=0)
1.333 + val|=bits>>(32-(iCount+aSize))<<(-iCount); // scrub low order bits
1.334 +#else
1.335 + val|=bits>>(32-(iCount+aSize))<<(-iCount); // scrub low order bits
1.336 +#endif
1.337 + aSize=-iCount; // bits still required
1.338 + if (iRemain>0)
1.339 + {
1.340 + bits=reverse(*iPtr++);
1.341 + iCount+=32;
1.342 + iRemain-=32;
1.343 + if (iRemain<0)
1.344 + iCount+=iRemain;
1.345 + }
1.346 + else
1.347 + {
1.348 + UnderflowL();
1.349 + bits=iBits;
1.350 + iCount-=aSize;
1.351 + }
1.352 + }
1.353 +#ifdef __CPU_X86
1.354 + // X86 does not allow shift-by-32
1.355 + iBits=aSize==32?0:bits<<aSize;
1.356 +#else
1.357 + iBits=bits<<aSize;
1.358 +#endif
1.359 + return val|(bits>>(32-aSize));
1.360 + }
1.361 +
1.362 +/** Read and decode a Huffman Code
1.363 +
1.364 + Interpret the next bits in the input as a Huffman code in the specified
1.365 + decoding. The decoding tree should be the output from Huffman::Decoding().
1.366 +
1.367 + @param aTree The huffman decoding tree
1.368 +
1.369 + @return The symbol that was decoded
1.370 +
1.371 + @leave "UnderflowL()" It the bit stream is exhausted more UnderflowL is called
1.372 + to get more data
1.373 +*/
1.374 +EXPORT_C TUint TBitInput::HuffmanL(const TUint32* aTree)
1.375 + {
1.376 + TUint huff=0;
1.377 + do
1.378 + {
1.379 + aTree=PtrAdd(aTree,huff>>16);
1.380 + huff=*aTree;
1.381 + if (ReadL()==0)
1.382 + huff<<=16;
1.383 + } while ((huff&0x10000u)==0);
1.384 + return huff>>17;
1.385 + }
1.386 +
1.387 +#endif
1.388 +
1.389 +/** Handle an empty input buffer
1.390 +
1.391 + This virtual function is called when the input buffer is empty and
1.392 + more bits are required. It should reset the input buffer with more
1.393 + data using Set().
1.394 +
1.395 + A derived class can replace this to read the data from a file
1.396 + (for example) before reseting the input buffer.
1.397 +
1.398 + @leave KErrUnderflow The default implementation leaves
1.399 +*/
1.400 +void TBitInput::UnderflowL()
1.401 + {
1.402 + User::Leave(KErrUnderflow);
1.403 + }