/*
c++ --version; c++ -std=c++14 -g stlcost.cpp && ./a.out && rm ./a.out
Apple LLVM version 10.0.1 (clang-1001.0.46.4)
Target: x86_64-apple-darwin18.6.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin

iteration 0 -----------------------------------------

malloc():
InitImage: 6.111393 ms
MakeMips: 5.444773 ms

std::array:
InitImage: 5.191247 ms (0.85x)
MakeMips: 21.877937 ms (4x)

std::vector:
InitImage: 31.074629 ms (5.1x)
MakeMips: 22.224956 ms (4.1x)

iteration 1 -----------------------------------------

malloc():
InitImage: 16.152593 ms (2.6x)
MakeMips: 15.258340 ms (2.8x)

std::array:
InitImage: 6.697883 ms (1.1x)
MakeMips: 29.992644 ms (5.5x)

std::vector:
InitImage: 61.089039 ms (10x)
MakeMips: 34.484021 ms (6.3x)

iteration 2 -----------------------------------------

malloc():
InitImage: 2.333101 ms (0.38x)
MakeMips: 5.921506 ms (1.1x)

std::array:
InitImage: 16.481657 ms (2.7x)
MakeMips: 20.485178 ms (3.8x)

std::vector:
InitImage: 27.512777 ms (4.5x)
MakeMips: 18.223748 ms (3.3x)
*/

///usr/bin/env \
    [ -n "${PATHEXT}" ] && ext='.exe'; \
    bin="$(dirname $0)/$(basename ${0%.*})$ext"; \
    c++ -std=c++14 -g -Werror -o $bin $0 \
    && $bin "$@"; \
    status=$?; \
    rm $bin; \
    exit $status

// the size of the image that is made into mips
#define IMAGE_SIZE() 512

typedef float ChannelType;

#include <stdio.h>
#include <array>
#include <vector>
#include <chrono>

struct ScopedTimer
{
    ScopedTimer(double& baseline, const char* label)
    : m_baseline(baseline)
    {
        printf("%s: ", label);
        m_start = std::chrono::high_resolution_clock::now();
    }

    ~ScopedTimer()
    {
        std::chrono::high_resolution_clock::time_point end = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double> duration = std::chrono::duration_cast<std::chrono::duration<double>>(end - m_start);
        const double elapsed = duration.count();
        if (m_baseline == 0) {
            printf("%f ms\n", elapsed * 1000.0);
            m_baseline = elapsed;
        } else {
            printf("%f ms (%0.2gx)\n", elapsed * 1000.0, elapsed / m_baseline);
        }
    }

    std::chrono::high_resolution_clock::time_point m_start;
    double& m_baseline;
};

// calculate the total number of pixels needed to hold the image of size IMAGE_SIZE() as well as all the mips
constexpr size_t TotalPixelsMipped()
{
    size_t ret = 0;
    size_t size = IMAGE_SIZE();
    while (size)
    {
        ret += size * size;
        size /= 2;
    }
    return ret;
}

constexpr size_t TotalChannelsMipped()
{
    // RGBA
    return TotalPixelsMipped() * 4;
}

constexpr size_t NumMips()
{
    size_t ret = 0;
    size_t size = IMAGE_SIZE();
    while (size)
    {
        ret++;
        size /= 2;
    }
    return ret;
}

void GetMipInfo(size_t desiredMipIndex, size_t& offset, size_t& width)
{
    offset = 0;
    width = IMAGE_SIZE();

    for (size_t mipIndex = 0; mipIndex < desiredMipIndex; ++mipIndex)
    {
        offset += width * width * 4;
        width /= 2;
    }
}

template<typename T>
void MakeMip(T& image, size_t mipIndex)
{
    size_t srcOffset;
    size_t srcWidth;
    GetMipInfo(mipIndex - 1, srcOffset, srcWidth);

    size_t destOffset;
    size_t destWidth;
    GetMipInfo(mipIndex, destOffset, destWidth);

    for (size_t destY = 0; destY < destWidth; ++destY)
    {
        for (size_t destX = 0; destX < destWidth; ++destX)
        {
            for (size_t channel = 0; channel < 4; ++channel)
            {
                // 2x2 box filter source mip pixels
                float value =
                    float(image[((destY * 2 + 0) * srcWidth + destX * 2 + 0) * 4 + srcOffset] + channel) +
                    float(image[((destY * 2 + 0) * srcWidth + destX * 2 + 1) * 4 + srcOffset] + channel) +
                    float(image[((destY * 2 + 1) * srcWidth + destX * 2 + 0) * 4 + srcOffset] + channel) +
                    float(image[((destY * 2 + 1) * srcWidth + destX * 2 + 1) * 4 + srcOffset] + channel);
                image[destOffset] = ChannelType(value / 4.0f);
                destOffset++;
            }
        }
    }
}

template<typename T>
void MakeMips(T& image)
{
    size_t mipCount = NumMips();
    for (size_t mipIndex = 1; mipIndex < mipCount; ++mipIndex)
        MakeMip(image, mipIndex);
}

template<typename T>
void InitImage(T& image)
{
    memset(&image[0], 0, TotalChannelsMipped() * sizeof(ChannelType));

    // It doesn't matter what we put into the image since we aren't ever looking at it, but initializing it anyhow.
    size_t i = 0;
    for (size_t y = 0; y < IMAGE_SIZE(); ++y)
    {
        for (size_t x = 0; x < IMAGE_SIZE(); ++x)
        {
            image[i * 4 + 0] = ChannelType(x % 256);
            image[i * 4 + 1] = ChannelType(y % 256);
            image[i * 4 + 2] = ChannelType(0);
            image[i * 4 + 3] = ChannelType(255);
            i++;
        }
    }
}

int main(void)
{

    double init_image_baseline = 0, make_mips_baseline = 0;

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

        printf("\niteration %i -----------------------------------------\n", i);

        // c array
        {
            ChannelType* carray;
            printf("\nmalloc():\n");
            {
                ScopedTimer timer(init_image_baseline, "InitImage");
                carray = (ChannelType*)malloc(sizeof(ChannelType)*TotalChannelsMipped());
                InitImage(carray);
            }
            {
                ScopedTimer timer(make_mips_baseline, "MakeMips");
                MakeMips(carray);
            }
            free(carray);
        }

        // std::array
        // dynamically allocated to avoid a stack overflow
        {
            std::array<ChannelType, TotalChannelsMipped()>* array_ptr = new std::array<ChannelType, TotalChannelsMipped()>;
            std::array<ChannelType, TotalChannelsMipped()>& array = *array_ptr;
            printf("\nstd::array:\n");
            {
                ScopedTimer timer(init_image_baseline, "InitImage");
                InitImage(array);
            }
            {
                ScopedTimer timer(make_mips_baseline, "MakeMips");
                MakeMips(array);
            }
            delete(array_ptr);
        }

        // std::vector
        {
            std::vector<ChannelType> vector;
            printf("\nstd::vector:\n");
            {
                ScopedTimer timer(init_image_baseline, "InitImage");
                vector.resize(TotalChannelsMipped());
                InitImage(vector);
            }
            {
                ScopedTimer timer(make_mips_baseline, "MakeMips");
                MakeMips(vector);
            }
        }
    }

    #ifdef _MSC_VER
    system("pause");
    #endif
    return 0;
}