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

//

// 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.

//

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

//

// A program to generate various acceleration lookup tables 

// for Imf::DwaCompressor

//

#include <cstddef>

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#include <vector>

#include <OpenEXRConfig.h>

#ifdef OPENEXR_IMF_HAVE_SYSCONF_NPROCESSORS_ONLN

#include <unistd.h>

#endif

#include <half.h>

#include <IlmThread.h>

#include <IlmThreadSemaphore.h>

#include <ImfIO.h>

#include <ImfXdr.h>

#include "ImfNamespace.h"

using namespace OPENEXR_IMF_NAMESPACE;

namespace {

    class LutHeaderWorker

    {

        public:

            class Runner : public IlmThread::Thread

            {

                public:

                    Runner(LutHeaderWorker &worker, bool output):

                        IlmThread::Thread(),

                        _worker(worker),

                        _output(output)

                    {

                        start();

                    }

                    virtual ~Runner()

                    {

                        _semaphore.wait();

                    }

                    virtual void run()

                    {

                        _semaphore.post();

                        _worker.run(_output);

                    }

                private:

                    LutHeaderWorker     &_worker;

                    bool                 _output;

                    IlmThread::Semaphore _semaphore;

            }; // class LutHeaderWorker::Runner

            LutHeaderWorker(size_t startValue,

                            size_t endValue):

                _lastCandidateCount(0),

                _startValue(startValue),

                _endValue(endValue),

                _numElements(0),

                _offset(new size_t[numValues()]),

                _elements(new unsigned short[1024*1024*2])

            {

            }

            ~LutHeaderWorker()

            {

                delete[] _offset;

                delete[] _elements;

            }

            size_t lastCandidateCount() const

            {

                return _lastCandidateCount;

            }

            size_t numValues() const 

            {

                return _endValue - _startValue;

            }

            size_t numElements() const

            {

                return _numElements;

            }

            const size_t* offset() const

            {

                return _offset;

            }

            const unsigned short* elements() const

            {

                return _elements;

            }

            void run(bool outputProgress)

            {

                half candidate[16];

                int  candidateCount = 0;

                for (size_t input=_startValue; input<_endValue; ++input) {

                    if (outputProgress) {

#ifdef __GNUC__

                        if (input % 100 == 0) {

                            fprintf(stderr, 

                            " Building acceleration for DwaCompressor, %.2f %%      %c",

                                          100.*(float)input/(float)numValues(), 13);

                        }

#else

                        if (input % 1000 == 0) {

                            fprintf(stderr, 

                            " Building acceleration for DwaCompressor, %.2f %%\n",

                                          100.*(float)input/(float)numValues());

                        }

#endif

                    } 

                    int  numSetBits = countSetBits(input);

                    half inputHalf, closestHalf;

                    inputHalf.setBits(input);

                    _offset[input - _startValue] = _numElements;

                    // Gather candidates

                    candidateCount = 0;

                    for (int targetNumSetBits=numSetBits-1; targetNumSetBits>=0;

                                                           --targetNumSetBits) {

                        bool valueFound = false;

                        for (int i=0; i<65536; ++i) {

                            if (countSetBits(i) != targetNumSetBits) continue;

                            if (!valueFound) {

                                closestHalf.setBits(i);

                                valueFound = true;

                            } else {

                                half tmpHalf;

                                tmpHalf.setBits(i);

                                if (fabs((float)inputHalf - (float)tmpHalf) < 

                                    fabs((float)inputHalf - (float)closestHalf)) {

                                    closestHalf = tmpHalf;

                                }

                            }

                        }

                        if (valueFound == false) {

                            fprintf(stderr, "bork bork bork!\n");

                        }       

                        candidate[candidateCount] = closestHalf;

                        candidateCount++;

                    }

                    // Sort candidates by increasing number of bits set

                    for (int i=0; i

                        for (int j=i+1; j

                            int   iCnt = countSetBits(candidate[i].bits());

                            int   jCnt = countSetBits(candidate[j].bits());

                            if (jCnt < iCnt) {

                                half tmp     = candidate[i];

                                candidate[i] = candidate[j];

                                candidate[j] = tmp;

                            }

                        }

                    }

                    // Copy candidates to the data buffer;

                    for (int i=0; i

                        _elements[_numElements] = candidate[i].bits();

                        _numElements++;

                    }

                    if (input == _endValue-1) {

                        _lastCandidateCount = candidateCount;

                    }

                }

            }

        private:

            size_t          _lastCandidateCount;

            size_t          _startValue;

            size_t          _endValue;

            size_t          _numElements;

            size_t         *_offset;

            unsigned short *_elements;

            //

            // Precomputing the bit count runs faster than using

            // the builtin instruction, at least in one case..

            //

            // Precomputing 8-bits is no slower than 16-bits,

            // and saves a fair bit of overhead..

            //

            int countSetBits(unsigned short src)

            {

                static const unsigned short numBitsSet[256] =

                {

                    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,

                    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

                    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

                    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

                    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

                    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

                    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

                    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

                    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

                    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

                    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

                    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

                    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

                    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

                    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

                    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8

                };

                return numBitsSet[src & 0xff] + numBitsSet[src >> 8];

            }

    }; // class LutHeaderWorker

} // namespace

//

// Generate a no-op LUT, to cut down in conditional branches

//

void

generateNoop()

{

    printf("const unsigned short dwaCompressorNoOp[] = \n");

    printf("{");

    for (int i=0; i<65536; ++i) {

        if (i % 8 == 0) {

            printf("\n    ");

        }

        unsigned short dst;

        char *tmp = (char *)(&dst);

        unsigned short src = (unsigned short)i;

        Xdr::write <CharPtrIO> (tmp,  src);

        printf("0x%04x, ", dst);

    }

    printf("\n};\n");

}

//

// Nonlinearly encode luminance. For values below 1.0, we want

// to use a gamma 2.2 function to match what is fairly common

// for storing output referred. However, > 1, gamma functions blow up,

// and log functions are much better behaved. We could use a log 

// function everywhere, but it tends to over-sample dark 

// regions and undersample the brighter regions, when 

// compared to the way real devices reproduce values.

//

// So, above 1, use a log function which is a smooth blend

// into the gamma function. 

//

//  Nonlinear(linear) = 

//

//    linear^(1./2.2)             / linear <= 1.0

//                               |

//    ln(linear)/ln(e^2.2) + 1    \ otherwise

//

//

// toNonlinear[] needs to take in XDR format half float values,

// and output NATIVE format float. 

//

// toLinear[] does the opposite - takes in NATIVE half and 

// outputs XDR half values.

//

void

generateToLinear()

{

    unsigned short toLinear[65536];

    toLinear[0] = 0;

    for (int i=1; i<65536; ++i) {

        half  h;

        float sign    = 1;

        float logBase = pow(2.7182818, 2.2);

        // map  NaN and inf to 0

        if ((i & 0x7c00) == 0x7c00) {

            toLinear[i]    = 0;

            continue;

        }

        //

        // _toLinear - assume i is NATIVE, but our output needs

        //             to get flipped to XDR

        //

        h.setBits(i);

        sign = 1;

        if ((float)h < 0) {

            sign = -1;

        } 

        if ( fabs( (float)h) <= 1.0 ) {

            h  = (half)(sign * pow((float)fabs((float)h), 2.2f));

        } else {

            h  = (half)(sign * pow(logBase, (float)(fabs((float)h) - 1.0)));

        }

        {

            char *tmp = (char *)(&toLinear[i]);

            Xdr::write <CharPtrIO> ( tmp,  h.bits());

        }

    }

    printf("const unsigned short dwaCompressorToLinear[] = \n");

    printf("{");

    for (int i=0; i<65536; ++i) {

        if (i % 8 == 0) {

            printf("\n    ");

        }

        printf("0x%04x, ", toLinear[i]);

    }

    printf("\n};\n");

}

void

generateToNonlinear()

{

    unsigned short toNonlinear[65536];

    toNonlinear[0] = 0;

    for (int i=1; i<65536; ++i) {

        unsigned short usNative, usXdr;

        half  h;

        float sign    = 1;

        float logBase = pow(2.7182818, 2.2);

        usXdr           = i;

        {

            const char *tmp = (char *)(&usXdr);

            Xdr::read<CharPtrIO>(tmp, usNative);

        }

        // map  NaN and inf to 0

        if ((usNative & 0x7c00) == 0x7c00) {

            toNonlinear[i] = 0;

            continue;

        }

        //

        // toNonlinear - assume i is XDR

        //

        h.setBits(usNative);

        sign = 1;

        if ((float)h < 0) {

            sign = -1;

        } 

        if ( fabs( (float)h ) <= 1.0) {

            h = (half)(sign * pow(fabs((float)h), 1.f/2.2f));

        } else {

            h = (half)(sign * ( log(fabs((float)h)) / log(logBase) + 1.0) );

        }

        toNonlinear[i] = h.bits();

    }

    printf("const unsigned short dwaCompressorToNonlinear[] = \n");

    printf("{");

    for (int i=0; i<65536; ++i) {

        if (i % 8 == 0) {

            printf("\n    ");

        }

        printf("0x%04x, ", toNonlinear[i]);

    }

    printf("\n};\n");

}

//

// Attempt to get available CPUs in a somewhat portable way. 

//

int

cpuCount()

{

    if (!IlmThread::supportsThreads()) return 1;

    int cpuCount = 1;

#if defined (OPENEXR_IMF_HAVE_SYSCONF_NPROCESSORS_ONLN)

    cpuCount = sysconf(_SC_NPROCESSORS_ONLN);

#elif defined (_WIN32)

    SYSTEM_INFO sysinfo;

    GetSystemInfo( &sysinfo );

    cpuCount = sysinfo.dwNumberOfProcessors;

#endif

    if (cpuCount < 1) cpuCount = 1;

    return cpuCount;

}

//

// Generate acceleration luts for the quantization.

//

// For each possible input value, we want to find the closest numbers

// which have one fewer bits set than before. 

//

// This gives us num_bits(input)-1 values per input. If we alloc

// space for everything, that's like a 2MB table. We can do better

// by compressing all the values to be contigious and using offset

// pointers.

//

// After we've found the candidates with fewer bits set, sort them

// based on increasing numbers of bits set. This way, on quantize(),

// we can scan through the list and halt once we find the first

// candidate within the error range. For small values that can 

// be quantized to 0, 0 is the first value tested and the search

// can exit fairly quickly.

//

void

generateLutHeader()

{

    std::vector<LutHeaderWorker*> workers;

    size_t numWorkers     = cpuCount();

    size_t workerInterval = 65536 / numWorkers;

    for (size_t i=0; i

        if (i != numWorkers-1) {

            workers.push_back( new LutHeaderWorker( i   *workerInterval, 

                                                   (i+1)*workerInterval) );

        } else {

            workers.push_back( new LutHeaderWorker(i*workerInterval, 65536) );

        }

    }

    if (IlmThread::supportsThreads()) {

        std::vector<LutHeaderWorker::Runner*> runners;

        for (size_t i=0; i

            runners.push_back( new LutHeaderWorker::Runner(*workers[i], (i==0)) );

        }

        for (size_t i=0; i

            delete runners[i];

        }

    } else {

        for (size_t i=0; i

            workers[i]->run(i == 0);

        }

    }

    printf("static unsigned int closestDataOffset[] = {\n");

    int offsetIdx  = 0;

    int offsetPrev = 0;

    for (size_t i=0; i

        for (size_t value=0; value<workers[i]->numValues(); ++value) {

            if (offsetIdx % 8 == 0) {

                printf("    ");

            }

            printf("%6lu, ", workers[i]->offset()[value] + offsetPrev);

            if (offsetIdx % 8 == 7) {

                printf("\n");

            }

            offsetIdx++;

        }

        offsetPrev += workers[i]->offset()[workers[i]->numValues()-1] + 

                      workers[i]->lastCandidateCount();

    }

    printf("};\n\n\n");

    printf("static unsigned short closestData[] = {\n");

    int elementIdx = 0;

    for (size_t i=0; i

        for (size_t element=0; element<workers[i]->numElements(); ++element) {

            if (elementIdx % 8 == 0) {

                printf("    ");

            }

            printf("%5d, ", workers[i]->elements()[element]);

            if (elementIdx % 8 == 7) {

                printf("\n");

            }

            elementIdx++;

        }    

    }

    printf("};\n\n\n");

    for (size_t i=0; i

        delete workers[i];

    }

}

int

main(int argc, char **argv)

{

    printf("#include <cstddef>\n");

    printf("\n\n\n");

    generateNoop();

    printf("\n\n\n");

    generateToLinear();

    printf("\n\n\n");

    generateToNonlinear();

    printf("\n\n\n");

    generateLutHeader();

    return 0;

}