1 /*

     2 * Copyright (c) 2002-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 * Name        : CDeflate.h

    16 * Part of     : deflatecomp / deflatecomp

    17 * deflate compressor header file.

    18 * Version     : 1.0

    19 *

    20 */

    21 

    22 

    23 

    24 

    25 /**

    26  @internalComponent

    27 */

    28 

    29 #ifndef CDEFLATE_H

    30 #define CDEFLATE_H

    31 

    32 class CSigCompDeflateContext;

    33 class CMessageWriter;

    34 

    35 const TInt KMaxBits = 15;

    36 const TInt KLengthCodes = 29;

    37 const TInt KLiterals = 256;

    38 const TInt KLiteralCodes = (KLiterals + 1 + KLengthCodes);

    39 const TInt KDistanceCodes = 30;

    40 const TInt KMinMatch = 3;

    41 const TInt KMaxMatch = 258;

    42 const TUint KEncodeDistance = 256;

    43 

    44 /** length of good match, search stops after one of this length

    45 has been found

    46 */

    47 const TInt KGoodMatchLength = 16;

    48 

    49 /** length of nice match, chainlength will be reduced if one of

    50 this length has been found

    51 */

    52 const TInt KNiceMatchLength = 8;

    53 

    54 /** Do not perform lazy matching if we found match of this length

    55 */

    56 const TInt KNiceLazyMatchLength = 16;

    57 

    58 

    59 /** maximum number of chains linked to one hash table entry */

    60 const TInt KMaxChainLength = 32;

    61 

    62 /*

    63 number of bits for hash table. hash table size = 1<<KHashTableBits

    64 the lower this number is, the slower compression is (because of

    65 bigger possibility of conflicts in hashing) but lower the memory consumption

    66 15 is probably the bigger reasonable number, 8 lower.

    67 */

    68 const TInt KHashTableBits = 10;

    69 

    70 /**

    71  * @brief Class for deflate compressor definition.

    72  *

    73  * From RFC 1951:

    74  * The compressor uses a chained hash table to find duplicated strings,

    75  * using a hash function that operates on 3-byte sequences.  At any

    76  * given point during compression, let XYZ be the next 3 input bytes to

    77  * be examined (not necessarily all different, of course).  First, the

    78  * compressor examines the hash chain for XYZ.  If the chain is empty,

    79  * the compressor simply writes out X as a literal byte and advances one

    80  * byte in the input.  If the hash chain is not empty, indicating that

    81  * the sequence XYZ (or, if we are unlucky, some other 3 bytes with the

    82  * same hash function value) has occurred recently, the compressor

    83  * compares all strings on the XYZ hash chain with the actual input data

    84  * sequence starting at the current point, and selects the longest

    85  * match.

    86  *

    87  * The compressor searches the hash chains starting with the most recent

    88  * strings, to favor small distances and thus take advantage of the

    89  * Huffman encoding. The hash chains are singly linked. There are no

    90  *  deletions from the hash chains; the algorithm simply discards matches

    91  *  that are too old.  To avoid a worst-case situation, very long hash

    92  *  chains are arbitrarily truncated at a certain length, determined by a

    93  *  run-time parameter.

    94  *

    95  *  To improve overall compression, the compressor optionally defers the

    96  *  selection of matches ("lazy matching"): after a match of length N has

    97  *  been found, the compressor searches for a longer match starting at

    98  *  the next input byte.  If it finds a longer match, it truncates the

    99  *  previous match to a length of one (thus producing a single literal

   100  *  byte) and then emits the longer match.  Otherwise, it emits the

   101  *  original match, and, as described above, advances N bytes before

   102  *  continuing.

   103  */

   104 class CDeflate : public CBase

   105     {

   106     public:

   107 

   108         /**

   109          * @brief huffman tree node

   110          */

   111         class TTreeNode

   112             {

   113             public:

   114                 /** actual value of this node */

   115                 TUint16 iBits;

   116                 /** number of bits this tree node uses */

   117                 TUint8 iLength;

   118             };

   119 

   120     public:

   121 

   122         /**

   123         * This function creates a new CDeflate object.

   124         * The function may leave with KErrNoMemory if there is

   125         * insufficient memory available.

   126         * 

   127         * @post compressor is ready to compress.

   128         * @returns A created CDeflate object.

   129         */ 

   130         static CDeflate* NewL(TBool aDynamic,

   131                               CSigCompDeflateContext* aContext);

   132 

   133         /**

   134         * This function creates a new CDeflate and places a pointer

   135         * to it onto the cleanup stack.

   136         *  

   137         * @post compressor is ready to compress.

   138         * @returns Pointer to a created CDeflate object.

   139         * The function may leave with KErrNoMemory if there is

   140         * insufficient memory available.

   141         */ 

   142         static CDeflate* NewLC(TBool aDynamic,

   143                                CSigCompDeflateContext* aContext);

   144 

   145         /**

   146         * Destructor of the object. Destroy object and all its members.

   147         * 

   148         */ 

   149         ~CDeflate();

   150 

   151         /**

   152         * Compress given data into aOutputBuffer.

   153         * @param aMessage message to be compressed

   154         * @param aOutputBuffer compressed message will be placed into

   155         * this buffer

   156         */

   157         void CompressL(const TDesC8& aMessage, CMessageWriter* aMessageWriter);

   158 

   159         /**

   160         * Reset the compressor.

   161         */

   162         void Reset(void);

   163 

   164         /**

   165         * Reset hash table

   166         */

   167         void ResetHashTable(void);

   168 

   169         /**

   170         * Set the given dictionary

   171         * @param aPtr pointer to memory containing dictionary

   172         * @param aSize size of the dictionary, in bytes

   173         */

   174         void SetDictionary(const TUint8* aPtr, TInt aSize);

   175 

   176         /**

   177         * Change the window size.

   178         * @param aWindowSize new window size.

   179         */

   180         void ChangeWindowSizeL(TInt aWindowSize);

   181     

   182     private:

   183         void ConstructL(TBool aDynamic, CSigCompDeflateContext* aContext);

   184 

   185         CDeflate();

   186 

   187         /**

   188         * Send n bits to a queue buffer.

   189         * 

   190         * @param aValue bits value

   191         * @param aLength number of bits to send,

   192         */ 

   193         void SendBitsL(TUint aValue, TUint aLength);

   194 

   195         /**

   196         * Flush all queued bits

   197         */ 

   198         void FlushBitsL();

   199 

   200         /**

   201         * Put one byte into output buffer.

   202         * 

   203         * @param aValue byte to store in output buffer.

   204         */ 

   205         void PutByteL(TUint8 aValue);

   206 

   207         /**

   208         * Encode literal value, using Literal huffman tree

   209         * 

   210         * @param aValue literal to encode

   211         */ 

   212         void EncodeLiteralL(TInt aValue);

   213 

   214         /**

   215         * Encode pair of distance and length

   216         * 

   217         * @param aDist distance of a match being encoded

   218         * @param aLength length of the match.

   219         */ 

   220         void EncodeDistanceLengthPairL(TUint aDist, TUint aLength);

   221 

   222         /**

   223         * This method searches matching substrings in encoded message

   224         * using the hash table.

   225         * 

   226         * @param aMatchPos position within current window of found match.

   227         *                  (if match was found).

   228         * @param aLength length reference

   229         *                (if match was found).

   230         *

   231         * @post if match was found aOffset and aLength are filled with correct

   232         *       values

   233         * @returns ETrue if match was found, EFalse if not,

   234         */ 

   235         TBool FindBestMatch(TInt& aMatchPos, TInt& aLength);

   236 

   237         /**

   238         * Fill window with aBytes characters from given pointer

   239         * @param aPtr pointer where to fetch data from

   240         * @param aBytes number of bytes to fetch

   241         *

   242         * @returns number of bytes fetched from given address.

   243         */

   244         TInt FillWindow(const TUint8* aPtr, TInt aBytes);

   245 

   246         /**

   247         * Calculate hash from three given characters

   248         * @param aA first character for hash 

   249         * @param aB second character for hash 

   250         * @param aC third character for hash 

   251         */

   252         TInt CalcHash(TUint8 aA, TUint8 aB, TUint8 aC) const;

   253 

   254         /**

   255         * Insert hash calculated from 3 characters at given address

   256         * to the hash table.

   257         * @param aPosition position within the iWindow from where 3

   258         * characters for the hash will be fetched from

   259         */

   260         void InsertHash(TInt aPosition);

   261 

   262     private:

   263         /** output bit buffer, encoded bitstream*/

   264         TUint iBitBuffer;

   265         

   266         /** number of bits currently stored in bit buffer */

   267         TUint iBitsQueued;

   268         

   269         /** size of hash table */

   270         TInt iHashSize;

   271         

   272         /** mask used when calculating hash */

   273         TUint iHashMask;

   274         

   275         /** shift used when calculating hash */

   276         TUint iHashShift;

   277         

   278         /** shift used when calculating hash */

   279         TUint iHashShift2;

   280         

   281         /** the hash table,used to speed up searching of matching substrings */

   282         CArrayFixFlat<TInt16>* iHashTable;

   283 

   284         /** number of bytes queued */

   285         TInt iLookAhead;

   286 

   287         /** array of nodes, those are used as linked elements in hash table */

   288         CArrayFixFlat<TInt16>* iChainNodes;

   289         

   290         /** modulo mask for chain nodes, iWindowSize - 1 */

   291         TInt iChainMask;

   292 

   293         /** output buffer, encoded bitstream is stored there */

   294         CMessageWriter* iMessageWriter;

   295 

   296         /** determines whenever compression is dynamic or not */

   297         TBool iDynamic;

   298         

   299         /** deflate compression context */

   300         CSigCompDeflateContext* iDeflateContext;

   301     };

   302 

   303 #endif