///////////////////////////////////////////////////////////////////////////

//

// Copyright (c) 2009-2014 DreamWorks Animation LLC. 

//

// All rights reserved.

//

// Redistribution and use in source and binary forms, with or without

// modification, are permitted provided that the following conditions are

// met:

// *       Redistributions of source code must retain the above copyright

// notice, this list of conditions and the following disclaimer.

// *       Redistributions in binary form must reproduce the above

// copyright notice, this list of conditions and the following disclaimer

// in the documentation and/or other materials provided with the

// distribution.

// *       Neither the name of DreamWorks Animation nor the names of

// its contributors may be used to endorse or promote products derived

// from this software without specific prior written permission.

//

// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

//

///////////////////////////////////////////////////////////////////////////

#ifndef INCLUDED_IMF_FAST_HUF_H

#define INCLUDED_IMF_FAST_HUF_H

#include "ImfInt64.h"

#include "ImfNamespace.h"

OPENEXR_IMF_INTERNAL_NAMESPACE_HEADER_ENTER

//

// Alternative Canonical Huffman decoder:

//

// Canonical Huffman decoder based on 'On the Implementation of Minimum

// Redundancy Prefix Codes' by Moffat and Turpin - highly recommended

// reading as a good description of the problem space, as well as 

// a fast decoding algorithm.

//

// The premise is that instead of working directly with the coded 

// symbols, we create a new ordering based on the frequency of symbols.

// Less frequent symbols (and thus longer codes) are ordered earler.

// We're calling the values in this ordering 'Ids', as oppsed to 

// 'Symbols' - which are the short values we eventually want decoded.

//

// With this new ordering, a few small tables can be derived ('base' 

// and 'offset') which drive the decoding. To cut down on the 

// linear scanning of these tables, you can add a small table

// to directly look up short codes (as you might in a traditional

// lookup-table driven decoder). 

//

// The decoder is meant to be compatible with the encoder (and decoder)

// in ImfHuf.cpp, just faster. For ease of implementation, this decoder

// should only be used on compressed bitstreams >= 128 bits long.

//

class FastHufDecoder

{

  public:

    //

    // Longest compressed code length that ImfHuf supports (58 bits)

    //

    static const int MAX_CODE_LEN = 58;

    //

    // Number of bits in our acceleration table. Should match all

    // codes up to TABLE_LOOKUP_BITS in length.

    //

    static const int TABLE_LOOKUP_BITS = 12;

    FastHufDecoder (const char*& table,

                    int numBytes,

                    int minSymbol,

                    int maxSymbol,

                    int rleSymbol);

    ~FastHufDecoder ();

    static bool enabled ();

    void decode (const unsigned char *src,

                 int numSrcBits,

                 unsigned short *dst,

                 int numDstElems);

  private:

    void  buildTables (Int64*, Int64*);

    void  refill (Int64&, int, Int64&, int&, const unsigned char *&, int&);

    Int64 readBits (int, Int64&, int&, const char *&);

    int             _rleSymbol;        // RLE symbol written by the encoder.

                                       // This could be 65536, so beware

                                       // when you use shorts to hold things.

    int             _numSymbols;       // Number of symbols in the codebook.

    unsigned char   _minCodeLength;    // Minimum code length, in bits.

    unsigned char   _maxCodeLength;    // Maximum code length, in bits.

    int            *_idToSymbol;       // Maps Ids to symbols. Ids are a symbol

                                       // ordering sorted first in terms of 

                                       // code length, and by code within

                                       // the same length. Ids run from 0

                                       // to mNumSymbols-1.

    Int64 _ljBase[MAX_CODE_LEN + 1];   // the 'left justified base' table.

                                       // Takes base[i] (i = code length)

                                       // and 'left justifies' it into an Int64

    Int64 _ljOffset[MAX_CODE_LEN +1 ]; // There are some other terms that can 

                                       // be folded into constants when taking

                                       // the 'left justified' decode path. This

                                       // holds those constants, indexed by

                                       // code length

    //

    // We can accelerate the 'left justified' processing by running the

    // top TABLE_LOOKUP_BITS through a LUT, to find the symbol and code

    // length. These are those acceleration tables.

    //

    // Even though our evental 'symbols' are ushort's, the encoder adds

    // a symbol to indicate RLE. So with a dense code book, we could

    // have 2^16+1 codes, so both mIdToSymbol and mTableSymbol need

    // to be bigger than 16 bits.

    //

    int            _tableSymbol[1 << TABLE_LOOKUP_BITS];

    unsigned char  _tableCodeLen[1 << TABLE_LOOKUP_BITS];

    Int64          _tableMin;

};

OPENEXR_IMF_INTERNAL_NAMESPACE_HEADER_EXIT

#endif