diff -r c55016431358 -r 0a7b44b10206 symport/e32/euser/us_encode.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/symport/e32/euser/us_encode.cpp Thu Jun 25 15:59:54 2009 +0100 @@ -0,0 +1,477 @@ +// Copyright (c) 1998-2009 Nokia Corporation and/or its subsidiary(-ies). +// All rights reserved. +// This component and the accompanying materials are made available +// under the terms of the License "Symbian Foundation License v1.0" +// which accompanies this distribution, and is available +// at the URL "http://www.symbianfoundation.org/legal/sfl-v10.html". +// +// Initial Contributors: +// Nokia Corporation - initial contribution. +// +// Contributors: +// +// Description: +// e32\euser\us_encode.cpp +// +// + +#include +#include +#include + +_LIT(KCat,"Huffman"); +// local definitions used for Huffman code generation +typedef TUint16 THuff; /** @internal */ +const THuff KLeaf=0x8000; /** @internal */ +struct TNode +/** @internal */ + { + TUint iCount; + THuff iLeft; + THuff iRight; + }; + +/** recursive function to calculate the code lengths from the node tree + + @internalComponent +*/ +void HuffmanLengthsL(TUint32* aLengths,const TNode* aNodes,TInt aNode,TInt aLen) + { + if (++aLen>Huffman::KMaxCodeLength) + User::Leave(KErrOverflow); + + const TNode& node=aNodes[aNode]; + TUint x=node.iLeft; + if (x&KLeaf) + aLengths[x&~KLeaf]=aLen; + else + HuffmanLengthsL(aLengths,aNodes,x,aLen); + x=node.iRight; + if (x&KLeaf) + aLengths[x&~KLeaf]=aLen; + else + HuffmanLengthsL(aLengths,aNodes,x,aLen); + } + +/** Insert the {aCount,aValue} pair into the already sorted array of nodes + + @internalComponent +*/ +void InsertInOrder(TNode* aNodes, TInt aSize, TUint aCount, TInt aVal) + { + // Uses Insertion sort following a binary search... + TInt l=0, r=aSize; + while (l < r) + { + TInt m = (l+r) >> 1; + if (aNodes[m].iCount0. No code has a length + } + else if (lCount==1) + { + // special case for a single value (always encode as "0") + aHuffman[nodes[0].iRight&~KLeaf]=1; + } + else + { + // Huffman algorithm: pair off least frequent nodes and reorder + // + do + { + --lCount; + TUint c=nodes[lCount].iCount + nodes[lCount-1].iCount; + nodes[lCount].iLeft=nodes[lCount-1].iRight; + // re-order the leaves now to reflect new combined frequency 'c' + InsertInOrder(nodes,lCount-1,c,lCount); + } while (lCount>1); + // generate code lengths in aHuffman[] + HuffmanLengthsL(aHuffman,nodes,1,0); + } + CleanupStack::PopAndDestroy(nodes); + + __ASSERT_DEBUG(IsValid(aHuffman,aNumCodes),User::Panic(KCat,EHuffmanInvalidCoding)); + } + +/** Validate a Huffman encoding + + This verifies that a Huffman coding described by the code lengths is valid. + In particular, it ensures that no code exceeds the maximum length and + that it is possible to generate a canonical coding for the specified lengths. + + @param aHuffman The table of code lengths as generated by Huffman::HuffmanL() + @param aNumCodes The number of codes in the table + + @return True if the code is valid, otherwise false +*/ +EXPORT_C TBool Huffman::IsValid(const TUint32 aHuffman[],TInt aNumCodes) + { + // The code is valid if one of the following holds: + // (a) the code exactly fills the 'code space' + // (b) there is only a single symbol with code length 1 + // (c) there are no encoded symbols + // + TUint remain=1<aHuffman;) + { + TInt len=*--p; + if (len>0) + { + totlen+=len; + if (len>KMaxCodeLength) + return EFalse; + TUint c=1<<(KMaxCodeLength-len); + if (c>remain) + return EFalse; + remain-=c; + } + } + + return remain==0 || totlen<=1; + } + +/** Create a canonical Huffman encoding table + + This generates the huffman codes used by TBitOutput::HuffmanL() to write huffman + encoded data. The input is table of code lengths, as generated by Huffman::HuffmanL() + and must represent a valid huffman code. + + @param aHuffman The table of code lengths as generated by Huffman::HuffmanL() + @param aNumCodes The number of codes in the table + @param aEncodeTable The table for the output huffman codes. This must be + the same size as the code-length table, and can safely be the same table + + @panic "USER ???" If the provided code is not a valid Huffman coding + + @see IsValid() + @see HuffmanL() +*/ +EXPORT_C void Huffman::Encoding(const TUint32 aHuffman[],TInt aNumCodes,TUint32 aEncodeTable[]) + { + __ASSERT_ALWAYS(IsValid(aHuffman,aNumCodes),User::Panic(KCat,EHuffmanInvalidCoding)); + + TFixedArray lenCount; + lenCount.Reset(); + + TInt ii; + for (ii=0;ii=0) + ++lenCount[len]; + } + + TFixedArray nextCode; + TUint code=0; + for (ii=0;ii0) + { + EncodeRunLengthL(aOutput,(aLength-1)>>1); + aOutput.HuffmanL(HuffmanEncoding[1-(aLength&1)]); + } + } + +/** Store a canonical huffman encoding in compact form + + As the encoding is canonical, only the code lengths of each code needs to be saved. + + Due to the nature of code length tables, these can usually be stored very compactly + by encoding the encoding itself, hence the use of the bit output stream. + + @param aOutput The output stream for the encoding + @param aHuffman The table of code lengths as generated by Huffman::HuffmanL() + @param aNumCodes The number of huffman codes in the table + + @leave TBitOutput::HuffmanL() +*/ +EXPORT_C void Huffman::ExternalizeL(TBitOutput& aOutput,const TUint32 aHuffman[],TInt aNumCodes) + { + // We assume that the code length table is generated by the huffman generator, + // in which case the maxmimum code length is 27 bits. + // + // We apply three transformations to the data: + // 1. the data goes through a move-to-front coder + // 2. apply a rle-0 coder which replace runs of '0' with streams of '0a' and '0b' + // 3. encode the result using a predefined (average) huffman coding + // + // This can be done in a single pass over the data, avoiding the need for additional + // memory. + // + // initialise the list for the MTF coder + TFixedArray list; + TInt i; + for (i=0;i0) + list[j+1]=list[j]; + list[1]=TUint8(last); + last=c; + } + } + // encod any remaining run-length + EncodeRunLengthL(aOutput,rl); + } + + +/** Construct a bit stream output object + + Following construction the bit stream is ready for writing bits, but will first call + OverflowL() as the output buffer is 'full'. A derived class can detect this state as + Ptr() will return null. +*/ +EXPORT_C TBitOutput::TBitOutput() + :iCode(0),iBits(-8),iPtr(0),iEnd(0) + {} + +/** Construct a bit stream output object over a buffer + + Data will be written to the buffer until it is full, at which point OverflowL() will + be called. This should handle the data and then can Set() again to reset the buffer + for further output. + + @param aBuf The buffer for output + @param aSize The size of the buffer in bytes +*/ +EXPORT_C TBitOutput::TBitOutput(TUint8* aBuf,TInt aSize) + :iCode(0),iBits(-8),iPtr(aBuf),iEnd(aBuf+aSize) + {} + +/** Write a huffman code + + This expects a huffman code value as generated by Huffman::Encoding() + + @param aHuffCode The huffman code write to the stream + + @leave OverflowL() If the output buffer is full, OverflowL() is called +*/ +EXPORT_C void TBitOutput::HuffmanL(TUint aHuffCode) + { + DoWriteL(aHuffCode<<(32-Huffman::KMaxCodeLength),aHuffCode>>Huffman::KMaxCodeLength); + } + +/** Write an arbitrary integer value + + Write an unsigned integer using the number of bits specified. Only + the low order bits of the value are written to the output, most + significant bit first. + + @param aValue The value to write to the stream + @param aLength The number of bits to output + + @leave OverflowL() If the output buffer is full, OverflowL() is called +*/ +EXPORT_C void TBitOutput::WriteL(TUint aValue,TInt aLength) + { + if (aLength) + DoWriteL(aValue<<=32-aLength,aLength); + } + +/** Pad the bitstream to the next byte boundary + + Terminate the bitstream by padding the last byte with the requested value. + Following this operation the bitstream can continue to be used, the data will + start at the next byte. + + @param aPadding The bit value to pad the final byte with + + @leave OverflowL() If the output buffer is full, OverflowL() is called +*/ +EXPORT_C void TBitOutput::PadL(TUint aPadding) + { + if (iBits>-8) + WriteL(aPadding?0xffffffffu:0,-iBits); + } + +/** Write the higher order bits to the stream + + @internalComponent +*/ +void TBitOutput::DoWriteL(TUint aBits,TInt aSize) + { + if (aSize>25) + { + // cannot process >25 bits in a single pass + // so do the top 8 bits first + ASSERT(aSize<=32); + DoWriteL(aBits&0xff000000u,8); + aBits<<=8; + aSize-=8; + } + + TInt bits=iBits; + TUint code=iCode|(aBits>>(bits+8)); + bits+=aSize; + if (bits>=0) + { + TUint8* p=iPtr; + do + { + if (p==iEnd) + { + // run out of buffer space so invoke the overflow handler + iPtr=p; + OverflowL(); + p=iPtr; + ASSERT(p!=iEnd); + } + *p++=TUint8(code>>24); + code<<=8; + bits-=8; + } while (bits>=0); + iPtr=p; + } + iCode=code; + iBits=bits; + } + +/** Handle a full output buffer + + This virtual function is called when the output buffer is full. It should deal + with the data in the buffer before reseting the buffer using Set(), allowing + further data to be written. + + A derived class can replace this to write the data to a file (for example) + before marking the buffer as empty. + + @leave KErrOverflow The default implementation leaves +*/ +void TBitOutput::OverflowL() + { + User::Leave(KErrOverflow); + }