/*
* Copyright (c) 2002-2009 Nokia Corporation and/or its subsidiary(-ies).
* All rights reserved.
* This component and the accompanying materials are made available
* under the terms of "Eclipse Public License v1.0"
* which accompanies this distribution, and is available
* at the URL "http://www.eclipse.org/legal/epl-v10.html".
*
* Initial Contributors:
* Nokia Corporation - initial contribution.
*
* Contributors:
*
* Description:
* Name        : CDeflate.h
* Part of     : deflatecomp / deflatecomp
* deflate compressor header file.
* Version     : 1.0
*
*/




/**
 @internalComponent
*/

#ifndef CDEFLATE_H
#define CDEFLATE_H

class CSigCompDeflateContext;
class CMessageWriter;

const TInt KMaxBits = 15;
const TInt KLengthCodes = 29;
const TInt KLiterals = 256;
const TInt KLiteralCodes = (KLiterals + 1 + KLengthCodes);
const TInt KDistanceCodes = 30;
const TInt KMinMatch = 3;
const TInt KMaxMatch = 258;
const TUint KEncodeDistance = 256;

/** length of good match, search stops after one of this length
has been found
*/
const TInt KGoodMatchLength = 16;

/** length of nice match, chainlength will be reduced if one of
this length has been found
*/
const TInt KNiceMatchLength = 8;

/** Do not perform lazy matching if we found match of this length
*/
const TInt KNiceLazyMatchLength = 16;


/** maximum number of chains linked to one hash table entry */
const TInt KMaxChainLength = 32;

/*
number of bits for hash table. hash table size = 1<<KHashTableBits
the lower this number is, the slower compression is (because of
bigger possibility of conflicts in hashing) but lower the memory consumption
15 is probably the bigger reasonable number, 8 lower.
*/
const TInt KHashTableBits = 10;

/**
 * @brief Class for deflate compressor definition.
 *
 * From RFC 1951:
 * The compressor uses a chained hash table to find duplicated strings,
 * using a hash function that operates on 3-byte sequences.  At any
 * given point during compression, let XYZ be the next 3 input bytes to
 * be examined (not necessarily all different, of course).  First, the
 * compressor examines the hash chain for XYZ.  If the chain is empty,
 * the compressor simply writes out X as a literal byte and advances one
 * byte in the input.  If the hash chain is not empty, indicating that
 * the sequence XYZ (or, if we are unlucky, some other 3 bytes with the
 * same hash function value) has occurred recently, the compressor
 * compares all strings on the XYZ hash chain with the actual input data
 * sequence starting at the current point, and selects the longest
 * match.
 *
 * The compressor searches the hash chains starting with the most recent
 * strings, to favor small distances and thus take advantage of the
 * Huffman encoding. The hash chains are singly linked. There are no
 *  deletions from the hash chains; the algorithm simply discards matches
 *  that are too old.  To avoid a worst-case situation, very long hash
 *  chains are arbitrarily truncated at a certain length, determined by a
 *  run-time parameter.
 *
 *  To improve overall compression, the compressor optionally defers the
 *  selection of matches ("lazy matching"): after a match of length N has
 *  been found, the compressor searches for a longer match starting at
 *  the next input byte.  If it finds a longer match, it truncates the
 *  previous match to a length of one (thus producing a single literal
 *  byte) and then emits the longer match.  Otherwise, it emits the
 *  original match, and, as described above, advances N bytes before
 *  continuing.
 */
class CDeflate : public CBase
    {
    public:

        /**
         * @brief huffman tree node
         */
        class TTreeNode
            {
            public:
                /** actual value of this node */
                TUint16 iBits;
                /** number of bits this tree node uses */
                TUint8 iLength;
            };

    public:

        /**
        * This function creates a new CDeflate object.
        * The function may leave with KErrNoMemory if there is
        * insufficient memory available.
        * 
        * @post compressor is ready to compress.
        * @returns A created CDeflate object.
        */ 
        static CDeflate* NewL(TBool aDynamic,
                              CSigCompDeflateContext* aContext);

        /**
        * This function creates a new CDeflate and places a pointer
        * to it onto the cleanup stack.
        *  
        * @post compressor is ready to compress.
        * @returns Pointer to a created CDeflate object.
        * The function may leave with KErrNoMemory if there is
        * insufficient memory available.
        */ 
        static CDeflate* NewLC(TBool aDynamic,
                               CSigCompDeflateContext* aContext);

        /**
        * Destructor of the object. Destroy object and all its members.
        * 
        */ 
        ~CDeflate();

        /**
        * Compress given data into aOutputBuffer.
        * @param aMessage message to be compressed
        * @param aOutputBuffer compressed message will be placed into
        * this buffer
        */
        void CompressL(const TDesC8& aMessage, CMessageWriter* aMessageWriter);

        /**
        * Reset the compressor.
        */
        void Reset(void);

        /**
        * Reset hash table
        */
        void ResetHashTable(void);

        /**
        * Set the given dictionary
        * @param aPtr pointer to memory containing dictionary
        * @param aSize size of the dictionary, in bytes
        */
        void SetDictionary(const TUint8* aPtr, TInt aSize);

        /**
        * Change the window size.
        * @param aWindowSize new window size.
        */
        void ChangeWindowSizeL(TInt aWindowSize);
    
    private:
        void ConstructL(TBool aDynamic, CSigCompDeflateContext* aContext);

        CDeflate();

        /**
        * Send n bits to a queue buffer.
        * 
        * @param aValue bits value
        * @param aLength number of bits to send,
        */ 
        void SendBitsL(TUint aValue, TUint aLength);

        /**
        * Flush all queued bits
        */ 
        void FlushBitsL();

        /**
        * Put one byte into output buffer.
        * 
        * @param aValue byte to store in output buffer.
        */ 
        void PutByteL(TUint8 aValue);

        /**
        * Encode literal value, using Literal huffman tree
        * 
        * @param aValue literal to encode
        */ 
        void EncodeLiteralL(TInt aValue);

        /**
        * Encode pair of distance and length
        * 
        * @param aDist distance of a match being encoded
        * @param aLength length of the match.
        */ 
        void EncodeDistanceLengthPairL(TUint aDist, TUint aLength);

        /**
        * This method searches matching substrings in encoded message
        * using the hash table.
        * 
        * @param aMatchPos position within current window of found match.
        *                  (if match was found).
        * @param aLength length reference
        *                (if match was found).
        *
        * @post if match was found aOffset and aLength are filled with correct
        *       values
        * @returns ETrue if match was found, EFalse if not,
        */ 
        TBool FindBestMatch(TInt& aMatchPos, TInt& aLength);

        /**
        * Fill window with aBytes characters from given pointer
        * @param aPtr pointer where to fetch data from
        * @param aBytes number of bytes to fetch
        *
        * @returns number of bytes fetched from given address.
        */
        TInt FillWindow(const TUint8* aPtr, TInt aBytes);

        /**
        * Calculate hash from three given characters
        * @param aA first character for hash 
        * @param aB second character for hash 
        * @param aC third character for hash 
        */
        TInt CalcHash(TUint8 aA, TUint8 aB, TUint8 aC) const;

        /**
        * Insert hash calculated from 3 characters at given address
        * to the hash table.
        * @param aPosition position within the iWindow from where 3
        * characters for the hash will be fetched from
        */
        void InsertHash(TInt aPosition);

    private:
        /** output bit buffer, encoded bitstream*/
        TUint iBitBuffer;
        
        /** number of bits currently stored in bit buffer */
        TUint iBitsQueued;
        
        /** size of hash table */
        TInt iHashSize;
        
        /** mask used when calculating hash */
        TUint iHashMask;
        
        /** shift used when calculating hash */
        TUint iHashShift;
        
        /** shift used when calculating hash */
        TUint iHashShift2;
        
        /** the hash table,used to speed up searching of matching substrings */
        CArrayFixFlat<TInt16>* iHashTable;

        /** number of bytes queued */
        TInt iLookAhead;

        /** array of nodes, those are used as linked elements in hash table */
        CArrayFixFlat<TInt16>* iChainNodes;
        
        /** modulo mask for chain nodes, iWindowSize - 1 */
        TInt iChainMask;

        /** output buffer, encoded bitstream is stored there */
        CMessageWriter* iMessageWriter;

        /** determines whenever compression is dynamic or not */
        TBool iDynamic;
        
        /** deflate compression context */
        CSigCompDeflateContext* iDeflateContext;
    };

#endif