1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/kernelhwsrv/kernel/eka/euser/us_encode.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,478 @@
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_encode.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 +
1.26 +_LIT(KCat,"Huffman");
1.27 +// local definitions used for Huffman code generation
1.28 +typedef TUint16 THuff; /** @internal */
1.29 +const THuff KLeaf=0x8000; /** @internal */
1.30 +struct TNode
1.31 +/** @internal */
1.32 + {
1.33 + TUint iCount;
1.34 + THuff iLeft;
1.35 + THuff iRight;
1.36 + };
1.37 +
1.38 +/** recursive function to calculate the code lengths from the node tree
1.39 +
1.40 + @internalComponent
1.41 +*/
1.42 +void HuffmanLengthsL(TUint32* aLengths,const TNode* aNodes,TInt aNode,TInt aLen)
1.43 + {
1.44 + if (++aLen>Huffman::KMaxCodeLength)
1.45 + User::Leave(KErrOverflow);
1.46 +
1.47 + const TNode& node=aNodes[aNode];
1.48 + TUint x=node.iLeft;
1.49 + if (x&KLeaf)
1.50 + aLengths[x&~KLeaf]=aLen;
1.51 + else
1.52 + HuffmanLengthsL(aLengths,aNodes,x,aLen);
1.53 + x=node.iRight;
1.54 + if (x&KLeaf)
1.55 + aLengths[x&~KLeaf]=aLen;
1.56 + else
1.57 + HuffmanLengthsL(aLengths,aNodes,x,aLen);
1.58 + }
1.59 +
1.60 +/** Insert the {aCount,aValue} pair into the already sorted array of nodes
1.61 +
1.62 + @internalComponent
1.63 +*/
1.64 +void InsertInOrder(TNode* aNodes, TInt aSize, TUint aCount, TInt aVal)
1.65 + {
1.66 + // Uses Insertion sort following a binary search...
1.67 + TInt l=0, r=aSize;
1.68 + while (l < r)
1.69 + {
1.70 + TInt m = (l+r) >> 1;
1.71 + if (aNodes[m].iCount<aCount)
1.72 + r=m;
1.73 + else
1.74 + l=m+1;
1.75 + }
1.76 + Mem::Copy(aNodes+l+1,aNodes+l,sizeof(TNode)*(aSize-l));
1.77 + aNodes[l].iCount=aCount;
1.78 + aNodes[l].iRight=TUint16(aVal);
1.79 + }
1.80 +
1.81 +/** Generate a Huffman code
1.82 +
1.83 + This generates a Huffman code for a given set of code frequencies. The output
1.84 + is a table of code lengths which can be used to build canonincal encoding tables
1.85 + or decoding trees for use with the TBitInput and TBitOutput classes.
1.86 +
1.87 + Entries in the table with a frequency of zero will have a zero code length
1.88 + and thus no associated huffman encoding. If each such symbol should have a
1.89 + maximum length encoding, they must be given at least a frequency of 1.
1.90 +
1.91 + For an alphabet of n symbols, this algorithm has a transient memory overhead
1.92 + of 8n, and a time complexity of O(n*log(n)).
1.93 +
1.94 + @param aFrequency The table of code frequencies
1.95 + @param aNumCodes The number of codes in the table
1.96 + @param aHuffman The table for the output code-length table. This must be
1.97 + the same size as the frequency table, and can safely be the same table
1.98 +
1.99 + @leave KErrNoMemory If memory used for code generation cannot be allocated
1.100 +
1.101 + @panic "USER ???" If the number of codes exceeds Huffman::KMaxCodes
1.102 +*/
1.103 +EXPORT_C void Huffman::HuffmanL(const TUint32 aFrequency[],TInt aNumCodes,TUint32 aHuffman[])
1.104 + {
1.105 + __ASSERT_ALWAYS(TUint(aNumCodes)<=TUint(KMaxCodes),User::Panic(KCat,EHuffmanTooManyCodes));
1.106 +
1.107 + // Sort the values into decreasing order of frequency
1.108 + //
1.109 + TNode* nodes = new(ELeave) TNode[aNumCodes];
1.110 + CleanupArrayDeletePushL(nodes);
1.111 + TInt lCount=0;
1.112 +
1.113 + for (TInt ii=0;ii<aNumCodes;++ii)
1.114 + {
1.115 + TInt c=aFrequency[ii];
1.116 + if (c!=0)
1.117 + InsertInOrder(nodes,lCount++,c,ii|KLeaf);
1.118 + }
1.119 +
1.120 + // default code length is zero
1.121 + Mem::FillZ(aHuffman,aNumCodes*sizeof(TUint32));
1.122 +
1.123 + if (lCount==0)
1.124 + {
1.125 + // no codes with frequency>0. No code has a length
1.126 + }
1.127 + else if (lCount==1)
1.128 + {
1.129 + // special case for a single value (always encode as "0")
1.130 + aHuffman[nodes[0].iRight&~KLeaf]=1;
1.131 + }
1.132 + else
1.133 + {
1.134 + // Huffman algorithm: pair off least frequent nodes and reorder
1.135 + //
1.136 + do
1.137 + {
1.138 + --lCount;
1.139 + TUint c=nodes[lCount].iCount + nodes[lCount-1].iCount;
1.140 + nodes[lCount].iLeft=nodes[lCount-1].iRight;
1.141 + // re-order the leaves now to reflect new combined frequency 'c'
1.142 + InsertInOrder(nodes,lCount-1,c,lCount);
1.143 + } while (lCount>1);
1.144 + // generate code lengths in aHuffman[]
1.145 + HuffmanLengthsL(aHuffman,nodes,1,0);
1.146 + }
1.147 + CleanupStack::PopAndDestroy(nodes);
1.148 +
1.149 + __ASSERT_DEBUG(IsValid(aHuffman,aNumCodes),User::Panic(KCat,EHuffmanInvalidCoding));
1.150 + }
1.151 +
1.152 +/** Validate a Huffman encoding
1.153 +
1.154 + This verifies that a Huffman coding described by the code lengths is valid.
1.155 + In particular, it ensures that no code exceeds the maximum length and
1.156 + that it is possible to generate a canonical coding for the specified lengths.
1.157 +
1.158 + @param aHuffman The table of code lengths as generated by Huffman::HuffmanL()
1.159 + @param aNumCodes The number of codes in the table
1.160 +
1.161 + @return True if the code is valid, otherwise false
1.162 +*/
1.163 +EXPORT_C TBool Huffman::IsValid(const TUint32 aHuffman[],TInt aNumCodes)
1.164 + {
1.165 + // The code is valid if one of the following holds:
1.166 + // (a) the code exactly fills the 'code space'
1.167 + // (b) there is only a single symbol with code length 1
1.168 + // (c) there are no encoded symbols
1.169 + //
1.170 + TUint remain=1<<KMaxCodeLength;
1.171 + TInt totlen=0;
1.172 + for (const TUint32* p=aHuffman+aNumCodes; p>aHuffman;)
1.173 + {
1.174 + TInt len=*--p;
1.175 + if (len>0)
1.176 + {
1.177 + totlen+=len;
1.178 + if (len>KMaxCodeLength)
1.179 + return EFalse;
1.180 + TUint c=1<<(KMaxCodeLength-len);
1.181 + if (c>remain)
1.182 + return EFalse;
1.183 + remain-=c;
1.184 + }
1.185 + }
1.186 +
1.187 + return remain==0 || totlen<=1;
1.188 + }
1.189 +
1.190 +/** Create a canonical Huffman encoding table
1.191 +
1.192 + This generates the huffman codes used by TBitOutput::HuffmanL() to write huffman
1.193 + encoded data. The input is table of code lengths, as generated by Huffman::HuffmanL()
1.194 + and must represent a valid huffman code.
1.195 +
1.196 + @param aHuffman The table of code lengths as generated by Huffman::HuffmanL()
1.197 + @param aNumCodes The number of codes in the table
1.198 + @param aEncodeTable The table for the output huffman codes. This must be
1.199 + the same size as the code-length table, and can safely be the same table
1.200 +
1.201 + @panic "USER ???" If the provided code is not a valid Huffman coding
1.202 +
1.203 + @see IsValid()
1.204 + @see HuffmanL()
1.205 +*/
1.206 +EXPORT_C void Huffman::Encoding(const TUint32 aHuffman[],TInt aNumCodes,TUint32 aEncodeTable[])
1.207 + {
1.208 + __ASSERT_ALWAYS(IsValid(aHuffman,aNumCodes),User::Panic(KCat,EHuffmanInvalidCoding));
1.209 +
1.210 + TFixedArray<TInt,KMaxCodeLength> lenCount;
1.211 + lenCount.Reset();
1.212 +
1.213 + TInt ii;
1.214 + for (ii=0;ii<aNumCodes;++ii)
1.215 + {
1.216 + TInt len=aHuffman[ii]-1;
1.217 + if (len>=0)
1.218 + ++lenCount[len];
1.219 + }
1.220 +
1.221 + TFixedArray<TUint,KMaxCodeLength> nextCode;
1.222 + TUint code=0;
1.223 + for (ii=0;ii<KMaxCodeLength;++ii)
1.224 + {
1.225 + code<<=1;
1.226 + nextCode[ii]=code;
1.227 + code+=lenCount[ii];
1.228 + }
1.229 +
1.230 + for (ii=0;ii<aNumCodes;++ii)
1.231 + {
1.232 + TInt len=aHuffman[ii];
1.233 + if (len==0)
1.234 + aEncodeTable[ii]=0;
1.235 + else
1.236 + {
1.237 + aEncodeTable[ii] = (nextCode[len-1]<<(KMaxCodeLength-len))|(len<<KMaxCodeLength);
1.238 + ++nextCode[len-1];
1.239 + }
1.240 + }
1.241 + }
1.242 +
1.243 +/** the encoding table for the externalised code
1.244 + @internalComponent
1.245 +*/
1.246 +const TUint32 HuffmanEncoding[]=
1.247 + {
1.248 + 0x10000000,
1.249 + 0x1c000000,
1.250 + 0x12000000,
1.251 + 0x1d000000,
1.252 + 0x26000000,
1.253 + 0x26800000,
1.254 + 0x2f000000,
1.255 + 0x37400000,
1.256 + 0x37600000,
1.257 + 0x37800000,
1.258 + 0x3fa00000,
1.259 + 0x3fb00000,
1.260 + 0x3fc00000,
1.261 + 0x3fd00000,
1.262 + 0x47e00000,
1.263 + 0x47e80000,
1.264 + 0x47f00000,
1.265 + 0x4ff80000,
1.266 + 0x57fc0000,
1.267 + 0x5ffe0000,
1.268 + 0x67ff0000,
1.269 + 0x77ff8000,
1.270 + 0x7fffa000,
1.271 + 0x7fffb000,
1.272 + 0x7fffc000,
1.273 + 0x7fffd000,
1.274 + 0x7fffe000,
1.275 + 0x87fff000,
1.276 + 0x87fff800
1.277 + };
1.278 +
1.279 +/** encode 0a as '0' and 0b as '1', return number of symbols created
1.280 +
1.281 + @internalComponent
1.282 +*/
1.283 +void EncodeRunLengthL(TBitOutput& aOutput, TInt aLength)
1.284 + {
1.285 + if (aLength>0)
1.286 + {
1.287 + EncodeRunLengthL(aOutput,(aLength-1)>>1);
1.288 + aOutput.HuffmanL(HuffmanEncoding[1-(aLength&1)]);
1.289 + }
1.290 + }
1.291 +
1.292 +/** Store a canonical huffman encoding in compact form
1.293 +
1.294 + As the encoding is canonical, only the code lengths of each code needs to be saved.
1.295 +
1.296 + Due to the nature of code length tables, these can usually be stored very compactly
1.297 + by encoding the encoding itself, hence the use of the bit output stream.
1.298 +
1.299 + @param aOutput The output stream for the encoding
1.300 + @param aHuffman The table of code lengths as generated by Huffman::HuffmanL()
1.301 + @param aNumCodes The number of huffman codes in the table
1.302 +
1.303 + @leave TBitOutput::HuffmanL()
1.304 +*/
1.305 +EXPORT_C void Huffman::ExternalizeL(TBitOutput& aOutput,const TUint32 aHuffman[],TInt aNumCodes)
1.306 + {
1.307 + // We assume that the code length table is generated by the huffman generator,
1.308 + // in which case the maxmimum code length is 27 bits.
1.309 + //
1.310 + // We apply three transformations to the data:
1.311 + // 1. the data goes through a move-to-front coder
1.312 + // 2. apply a rle-0 coder which replace runs of '0' with streams of '0a' and '0b'
1.313 + // 3. encode the result using a predefined (average) huffman coding
1.314 + //
1.315 + // This can be done in a single pass over the data, avoiding the need for additional
1.316 + // memory.
1.317 + //
1.318 + // initialise the list for the MTF coder
1.319 + TFixedArray<TUint8,Huffman::KMetaCodes> list;
1.320 + TInt i;
1.321 + for (i=0;i<list.Count();++i)
1.322 + list[i]=TUint8(i);
1.323 + TInt last=0;
1.324 +
1.325 + TInt rl=0;
1.326 + const TUint32* p32=aHuffman;
1.327 + const TUint32* e32=p32+aNumCodes;
1.328 + while (p32<e32)
1.329 + {
1.330 + TInt c=*p32++;
1.331 + if (c==last)
1.332 + ++rl; // repeat of last symbol
1.333 + else
1.334 + {
1.335 + // encode run-length
1.336 + EncodeRunLengthL(aOutput,rl);
1.337 + rl=0;
1.338 + // find code in MTF list
1.339 + TInt j;
1.340 + for (j=1;list[j]!=c;++j)
1.341 + ;
1.342 + // store this code
1.343 + aOutput.HuffmanL(HuffmanEncoding[j+1]);
1.344 + // adjust list for MTF algorithm
1.345 + while (--j>0)
1.346 + list[j+1]=list[j];
1.347 + list[1]=TUint8(last);
1.348 + last=c;
1.349 + }
1.350 + }
1.351 + // encod any remaining run-length
1.352 + EncodeRunLengthL(aOutput,rl);
1.353 + }
1.354 +
1.355 +
1.356 +/** Construct a bit stream output object
1.357 +
1.358 + Following construction the bit stream is ready for writing bits, but will first call
1.359 + OverflowL() as the output buffer is 'full'. A derived class can detect this state as
1.360 + Ptr() will return null.
1.361 +*/
1.362 +EXPORT_C TBitOutput::TBitOutput()
1.363 + :iCode(0),iBits(-8),iPtr(0),iEnd(0)
1.364 + {}
1.365 +
1.366 +/** Construct a bit stream output object over a buffer
1.367 +
1.368 + Data will be written to the buffer until it is full, at which point OverflowL() will
1.369 + be called. This should handle the data and then can Set() again to reset the buffer
1.370 + for further output.
1.371 +
1.372 + @param aBuf The buffer for output
1.373 + @param aSize The size of the buffer in bytes
1.374 +*/
1.375 +EXPORT_C TBitOutput::TBitOutput(TUint8* aBuf,TInt aSize)
1.376 + :iCode(0),iBits(-8),iPtr(aBuf),iEnd(aBuf+aSize)
1.377 + {}
1.378 +
1.379 +/** Write a huffman code
1.380 +
1.381 + This expects a huffman code value as generated by Huffman::Encoding()
1.382 +
1.383 + @param aHuffCode The huffman code write to the stream
1.384 +
1.385 + @leave OverflowL() If the output buffer is full, OverflowL() is called
1.386 +*/
1.387 +EXPORT_C void TBitOutput::HuffmanL(TUint aHuffCode)
1.388 + {
1.389 + DoWriteL(aHuffCode<<(32-Huffman::KMaxCodeLength),aHuffCode>>Huffman::KMaxCodeLength);
1.390 + }
1.391 +
1.392 +/** Write an arbitrary integer value
1.393 +
1.394 + Write an unsigned integer using the number of bits specified. Only
1.395 + the low order bits of the value are written to the output, most
1.396 + significant bit first.
1.397 +
1.398 + @param aValue The value to write to the stream
1.399 + @param aLength The number of bits to output
1.400 +
1.401 + @leave OverflowL() If the output buffer is full, OverflowL() is called
1.402 +*/
1.403 +EXPORT_C void TBitOutput::WriteL(TUint aValue,TInt aLength)
1.404 + {
1.405 + if (aLength)
1.406 + DoWriteL(aValue<<=32-aLength,aLength);
1.407 + }
1.408 +
1.409 +/** Pad the bitstream to the next byte boundary
1.410 +
1.411 + Terminate the bitstream by padding the last byte with the requested value.
1.412 + Following this operation the bitstream can continue to be used, the data will
1.413 + start at the next byte.
1.414 +
1.415 + @param aPadding The bit value to pad the final byte with
1.416 +
1.417 + @leave OverflowL() If the output buffer is full, OverflowL() is called
1.418 +*/
1.419 +EXPORT_C void TBitOutput::PadL(TUint aPadding)
1.420 + {
1.421 + if (iBits>-8)
1.422 + WriteL(aPadding?0xffffffffu:0,-iBits);
1.423 + }
1.424 +
1.425 +/** Write the higher order bits to the stream
1.426 +
1.427 + @internalComponent
1.428 +*/
1.429 +void TBitOutput::DoWriteL(TUint aBits,TInt aSize)
1.430 + {
1.431 + if (aSize>25)
1.432 + {
1.433 + // cannot process >25 bits in a single pass
1.434 + // so do the top 8 bits first
1.435 + ASSERT(aSize<=32);
1.436 + DoWriteL(aBits&0xff000000u,8);
1.437 + aBits<<=8;
1.438 + aSize-=8;
1.439 + }
1.440 +
1.441 + TInt bits=iBits;
1.442 + TUint code=iCode|(aBits>>(bits+8));
1.443 + bits+=aSize;
1.444 + if (bits>=0)
1.445 + {
1.446 + TUint8* p=iPtr;
1.447 + do
1.448 + {
1.449 + if (p==iEnd)
1.450 + {
1.451 + // run out of buffer space so invoke the overflow handler
1.452 + iPtr=p;
1.453 + OverflowL();
1.454 + p=iPtr;
1.455 + ASSERT(p!=iEnd);
1.456 + }
1.457 + *p++=TUint8(code>>24);
1.458 + code<<=8;
1.459 + bits-=8;
1.460 + } while (bits>=0);
1.461 + iPtr=p;
1.462 + }
1.463 + iCode=code;
1.464 + iBits=bits;
1.465 + }
1.466 +
1.467 +/** Handle a full output buffer
1.468 +
1.469 + This virtual function is called when the output buffer is full. It should deal
1.470 + with the data in the buffer before reseting the buffer using Set(), allowing
1.471 + further data to be written.
1.472 +
1.473 + A derived class can replace this to write the data to a file (for example)
1.474 + before marking the buffer as empty.
1.475 +
1.476 + @leave KErrOverflow The default implementation leaves
1.477 +*/
1.478 +void TBitOutput::OverflowL()
1.479 + {
1.480 + User::Leave(KErrOverflow);
1.481 + }