//  BlockyFroggy
//  Copyright © 2017 John Ryland.
//  All rights reserved.
#include "Image.h"
#include "Log.h"
#include <assert.h>
#include <math.h>
#include <stdint.h>
#include <stdio.h>


DECLARE_LOG_CONTEXT(PVR)


namespace PvrImage {

const unsigned char BILINEAR_FACTORS[16][4] =
{
	{ 4, 4, 4, 4 },
	{ 2, 6, 2, 6 },
	{ 8, 0, 8, 0 },
	{ 6, 2, 6, 2 },
	
	{ 2, 2, 6, 6 },
	{ 1, 3, 3, 9 },
	{ 4, 0, 12, 0 },
	{ 3, 1, 9, 3 },
	
	{ 8, 8, 0, 0 },
	{ 4, 12, 0, 0 },
	{ 16, 0, 0, 0 },
	{ 12, 4, 0, 0 },
	
	{ 6, 6, 2, 2 },
	{ 3, 9, 1, 3 },
	{ 12, 0, 4, 0 },
	{ 9, 3, 3, 1 },
};

// Weights are { colorA, colorB, alphaA, alphaB }
const unsigned char WEIGHTS[8][4] =
{
	// Weights for Mode=0
	{ 8, 0, 8, 0 },
	{ 5, 3, 5, 3 },
	{ 3, 5, 3, 5 },
	{ 0, 8, 0, 8 },
	
	// Weights for Mode=1
	{ 8, 0, 8, 0 },
	{ 4, 4, 4, 4 },
	{ 4, 4, 0, 0 },
	{ 0, 8, 0, 8 },
};

const unsigned short MORTON_TABLE[256] =
{
    0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, 0x0015,
    0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055,
    0x0100, 0x0101, 0x0104, 0x0105, 0x0110, 0x0111, 0x0114, 0x0115,
    0x0140, 0x0141, 0x0144, 0x0145, 0x0150, 0x0151, 0x0154, 0x0155,
    0x0400, 0x0401, 0x0404, 0x0405, 0x0410, 0x0411, 0x0414, 0x0415,
    0x0440, 0x0441, 0x0444, 0x0445, 0x0450, 0x0451, 0x0454, 0x0455,
    0x0500, 0x0501, 0x0504, 0x0505, 0x0510, 0x0511, 0x0514, 0x0515,
    0x0540, 0x0541, 0x0544, 0x0545, 0x0550, 0x0551, 0x0554, 0x0555,
    0x1000, 0x1001, 0x1004, 0x1005, 0x1010, 0x1011, 0x1014, 0x1015,
    0x1040, 0x1041, 0x1044, 0x1045, 0x1050, 0x1051, 0x1054, 0x1055,
    0x1100, 0x1101, 0x1104, 0x1105, 0x1110, 0x1111, 0x1114, 0x1115,
    0x1140, 0x1141, 0x1144, 0x1145, 0x1150, 0x1151, 0x1154, 0x1155,
    0x1400, 0x1401, 0x1404, 0x1405, 0x1410, 0x1411, 0x1414, 0x1415,
    0x1440, 0x1441, 0x1444, 0x1445, 0x1450, 0x1451, 0x1454, 0x1455,
    0x1500, 0x1501, 0x1504, 0x1505, 0x1510, 0x1511, 0x1514, 0x1515,
    0x1540, 0x1541, 0x1544, 0x1545, 0x1550, 0x1551, 0x1554, 0x1555,
    0x4000, 0x4001, 0x4004, 0x4005, 0x4010, 0x4011, 0x4014, 0x4015,
    0x4040, 0x4041, 0x4044, 0x4045, 0x4050, 0x4051, 0x4054, 0x4055,
    0x4100, 0x4101, 0x4104, 0x4105, 0x4110, 0x4111, 0x4114, 0x4115,
    0x4140, 0x4141, 0x4144, 0x4145, 0x4150, 0x4151, 0x4154, 0x4155,
    0x4400, 0x4401, 0x4404, 0x4405, 0x4410, 0x4411, 0x4414, 0x4415,
    0x4440, 0x4441, 0x4444, 0x4445, 0x4450, 0x4451, 0x4454, 0x4455,
    0x4500, 0x4501, 0x4504, 0x4505, 0x4510, 0x4511, 0x4514, 0x4515,
    0x4540, 0x4541, 0x4544, 0x4545, 0x4550, 0x4551, 0x4554, 0x4555,
    0x5000, 0x5001, 0x5004, 0x5005, 0x5010, 0x5011, 0x5014, 0x5015,
    0x5040, 0x5041, 0x5044, 0x5045, 0x5050, 0x5051, 0x5054, 0x5055,
    0x5100, 0x5101, 0x5104, 0x5105, 0x5110, 0x5111, 0x5114, 0x5115,
    0x5140, 0x5141, 0x5144, 0x5145, 0x5150, 0x5151, 0x5154, 0x5155,
    0x5400, 0x5401, 0x5404, 0x5405, 0x5410, 0x5411, 0x5414, 0x5415,
    0x5440, 0x5441, 0x5444, 0x5445, 0x5450, 0x5451, 0x5454, 0x5455,
    0x5500, 0x5501, 0x5504, 0x5505, 0x5510, 0x5511, 0x5514, 0x5515,
    0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555
};

const uint8_t BITSCALE_5_TO_8[32] = {
 0, 8, 16, 24, 32, 41, 49, 57, 65, 74,
 82, 90, 98, 106, 115, 123, 131, 139, 148, 156,
 164, 172, 180, 189, 197, 205, 213, 222, 230, 238,
 246, 255};

const uint8_t BITSCALE_4_TO_8[16] = {
 0, 17, 34, 51, 68, 85, 102, 119, 136, 153,
 170, 187, 204, 221, 238, 255};

const uint8_t BITSCALE_3_TO_8[8] = {
 0, 36, 72, 109, 145, 182, 218, 255};

const uint8_t BITSCALE_8_TO_5_FLOOR[256] = {
 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
 1, 1, 1, 1, 1, 1, 1, 2, 2, 2,
 2, 2, 2, 2, 2, 3, 3, 3, 3, 3,
 3, 3, 3, 4, 4, 4, 4, 4, 4, 4,
 4, 4, 5, 5, 5, 5, 5, 5, 5, 5,
 6, 6, 6, 6, 6, 6, 6, 6, 7, 7,
 7, 7, 7, 7, 7, 7, 8, 8, 8, 8,
 8, 8, 8, 8, 8, 9, 9, 9, 9, 9,
 9, 9, 9, 10, 10, 10, 10, 10, 10, 10,
 10, 11, 11, 11, 11, 11, 11, 11, 11, 12,
 12, 12, 12, 12, 12, 12, 12, 13, 13, 13,
 13, 13, 13, 13, 13, 13, 14, 14, 14, 14,
 14, 14, 14, 14, 15, 15, 15, 15, 15, 15,
 15, 15, 16, 16, 16, 16, 16, 16, 16, 16,
 17, 17, 17, 17, 17, 17, 17, 17, 17, 18,
 18, 18, 18, 18, 18, 18, 18, 19, 19, 19,
 19, 19, 19, 19, 19, 20, 20, 20, 20, 20,
 20, 20, 20, 21, 21, 21, 21, 21, 21, 21,
 21, 22, 22, 22, 22, 22, 22, 22, 22, 22,
 23, 23, 23, 23, 23, 23, 23, 23, 24, 24,
 24, 24, 24, 24, 24, 24, 25, 25, 25, 25,
 25, 25, 25, 25, 26, 26, 26, 26, 26, 26,
 26, 26, 26, 27, 27, 27, 27, 27, 27, 27,
 27, 28, 28, 28, 28, 28, 28, 28, 28, 29,
 29, 29, 29, 29, 29, 29, 29, 30, 30, 30,
 30, 30, 30, 30, 30, 31};

const uint8_t BITSCALE_8_TO_4_FLOOR[256] = {
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 1, 1, 1, 1, 2, 2, 2, 2, 2, 2,
 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
 2, 3, 3, 3, 3, 3, 3, 3, 3, 3,
 3, 3, 3, 3, 3, 3, 3, 3, 4, 4,
 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
 4, 4, 4, 4, 4, 5, 5, 5, 5, 5,
 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 5, 5, 6, 6, 6, 6, 6, 6, 6, 6,
 6, 6, 6, 6, 6, 6, 6, 6, 6, 7,
 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 7, 7, 7, 7, 7, 7, 8, 8, 8, 8,
 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 8, 8, 8, 9, 9, 9, 9, 9, 9, 9,
 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
 10, 10, 10, 10, 10, 10, 10, 11, 11, 11,
 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
 11, 11, 11, 11, 12, 12, 12, 12, 12, 12,
 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
 12, 13, 13, 13, 13, 13, 13, 13, 13, 13,
 13, 13, 13, 13, 13, 13, 13, 13, 14, 14,
 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
 14, 14, 14, 14, 14, 15};

const uint8_t BITSCALE_8_TO_3_FLOOR[256] = {
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 1, 1, 1, 2, 2, 2, 2, 2, 2, 2,
 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
 3, 3, 3, 3, 3, 3, 4, 4, 4, 4,
 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
 4, 4, 4, 5, 5, 5, 5, 5, 5, 5,
 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 5, 5, 5, 5, 5, 5, 5, 5, 5, 6,
 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 6, 6, 6, 6, 6, 7};

const uint8_t BITSCALE_8_TO_5_CEIL[256] = {
 0, 1, 1, 1, 1, 1, 1, 1, 1, 2,
 2, 2, 2, 2, 2, 2, 2, 3, 3, 3,
 3, 3, 3, 3, 3, 4, 4, 4, 4, 4,
 4, 4, 4, 5, 5, 5, 5, 5, 5, 5,
 5, 5, 6, 6, 6, 6, 6, 6, 6, 6,
 7, 7, 7, 7, 7, 7, 7, 7, 8, 8,
 8, 8, 8, 8, 8, 8, 9, 9, 9, 9,
 9, 9, 9, 9, 9, 10, 10, 10, 10, 10,
 10, 10, 10, 11, 11, 11, 11, 11, 11, 11,
 11, 12, 12, 12, 12, 12, 12, 12, 12, 13,
 13, 13, 13, 13, 13, 13, 13, 14, 14, 14,
 14, 14, 14, 14, 14, 14, 15, 15, 15, 15,
 15, 15, 15, 15, 16, 16, 16, 16, 16, 16,
 16, 16, 17, 17, 17, 17, 17, 17, 17, 17,
 18, 18, 18, 18, 18, 18, 18, 18, 18, 19,
 19, 19, 19, 19, 19, 19, 19, 20, 20, 20,
 20, 20, 20, 20, 20, 21, 21, 21, 21, 21,
 21, 21, 21, 22, 22, 22, 22, 22, 22, 22,
 22, 23, 23, 23, 23, 23, 23, 23, 23, 23,
 24, 24, 24, 24, 24, 24, 24, 24, 25, 25,
 25, 25, 25, 25, 25, 25, 26, 26, 26, 26,
 26, 26, 26, 26, 27, 27, 27, 27, 27, 27,
 27, 27, 27, 28, 28, 28, 28, 28, 28, 28,
 28, 29, 29, 29, 29, 29, 29, 29, 29, 30,
 30, 30, 30, 30, 30, 30, 30, 31, 31, 31,
 31, 31, 31, 31, 31, 31};

const uint8_t BITSCALE_8_TO_4_CEIL[256] = {
 0, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 2, 2,
 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
 2, 2, 2, 2, 2, 3, 3, 3, 3, 3,
 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
 4, 4, 4, 4, 4, 4, 4, 4, 4, 5,
 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 5, 5, 5, 5, 5, 5, 6, 6, 6, 6,
 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 6, 6, 6, 7, 7, 7, 7, 7, 7, 7,
 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 8, 8, 8, 8, 8, 8, 8, 9, 9, 9,
 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
 9, 9, 9, 9, 10, 10, 10, 10, 10, 10,
 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
 10, 11, 11, 11, 11, 11, 11, 11, 11, 11,
 11, 11, 11, 11, 11, 11, 11, 11, 12, 12,
 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
 12, 12, 12, 12, 12, 13, 13, 13, 13, 13,
 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
 13, 13, 14, 14, 14, 14, 14, 14, 14, 14,
 14, 14, 14, 14, 14, 14, 14, 14, 14, 15,
 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
 15, 15, 15, 15, 15, 15};

const uint8_t BITSCALE_8_TO_3_CEIL[256] = {
 0, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 2, 2, 2,
 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
 2, 2, 2, 3, 3, 3, 3, 3, 3, 3,
 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
 4, 4, 4, 4, 4, 4, 5, 5, 5, 5,
 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 5, 5, 5, 6, 6, 6, 6, 6, 6, 6,
 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 6, 6, 6, 6, 6, 6, 6, 6, 6, 7,
 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 7, 7, 7, 7, 7, 7};


/*

template<typename T, int dim>
class GenColor {
public:
    T v[dim];

    GenColor() {
      for (int i = 0; i < dim; i++)
        v[i] = 0;
    }

    GenColor(const GenColor<T,dim> &x) {
      for (int i = 0; i < dim; i++)
        v[i] = x.v[i];
    }

    GenColor<int,dim> operator *(int x) {
      GenColor<int,dim> res;
      for (int i = 0; i < dim; i++)
        res.v[i] = v[i] * x;
      return res;
    }

    GenColor<int,dim> operator +(const GenColor<T,dim> &x) const {
      GenColor<int,dim> res;
      for (int i = 0; i < dim; i++)
        res.v[i] = v[i] + x.v[i];
      return res;
    }

    GenColor<int,dim> operator -(const GenColor<T,dim> &x) const {
      GenColor<int,dim> res;
      for (int i = 0; i < dim; i++)
        res.v[i] = v[i] - x.v[i];
      return res;
    }

    int operator %(const GenColor<T,dim> &x) const {
      int res;
      for (int i = 0; i < dim; i++)
        res += v[i] * x.v[i];
      return res;
    }

    bool operator ==(const GenColor<T,dim> &x) const {
      for (int i = 0; i < dim; i++)
        if (v[i] != x.v[i])
          return false;
      return true;
    }

    bool operator !=(const GenColor<T,dim> &x) const {
      return !(*this == x);
    }

    void SetMin(const GenColor<T,dim> &x) {
      for (int i = 0; i < dim; i++)
        if (x.v[i] < v[i])
            v[i] = x.v[i];
    }

    void SetMax(const GenColor<T,dim> &x) {
      for (int i = 0; i < dim; i++)
        if (x.v[i] > v[i])
            v[i] = x.v[i];
    }
};


template<typename T>
class ColorRgb1 {
    union {
      struct {
        T b;
        T g;
        T r;
      };
      GenColor<T,3> gen;
    };
};

*/


template<typename T>
class ColorRgb {
public:
    union {
      struct {
        T b;
        T g;
        T r;
      };
      T v[3];
    };

    ColorRgb()
        : b(0)
        , g(0)
        , r(0) {
    }

    ColorRgb(T red, T green, T blue)
        : b(blue)
        , g(green)
        , r(red) {
    }

    ColorRgb(const ColorRgb<T> &x)
        : b(x.b)
        , g(x.g)
        , r(x.r) {
    }

    ColorRgb<int> operator *(int x) {
        return ColorRgb<int>(r * x, g * x, b * x);
    }

    ColorRgb<int> operator +(const ColorRgb<T> &x) const {
        return ColorRgb<int>(r + (int)x.r, g + (int)x.g, b + (int)x.b);
    }

    ColorRgb<int> operator -(const ColorRgb<T> &x) const {
        return ColorRgb<int>(r - (int)x.r, g - (int)x.g, b - (int)x.b);
    }

    int operator %(const ColorRgb<T> &x) const {
        return r * (int)x.r + g * (int)x.g + b * (int)x.b;
    }

    bool operator ==(const ColorRgb<T> &x) const {
        return r == x.r && g == x.g && b == x.b;
    }

    bool operator !=(const ColorRgb<T> &x) const {
        return r != x.r || g != x.g || b != x.b;
    }

    void SetMin(const ColorRgb<T> &x) {
      for (int i = 0; i < 3; i++)
        if (x.v[i] < v[i])
            v[i] = x.v[i];
    }

    void SetMax(const ColorRgb<T> &x) {
      for (int i = 0; i < 3; i++)
        if (x.v[i] > v[i])
            v[i] = x.v[i];
    }
};

template<typename T>
class ColorRgba : public ColorRgb<T> {
public:
    T a;

    ColorRgba() :
        a(0) {
    }

    ColorRgba(T red, T green, T blue, T alpha)
        : ColorRgb<T>(red, green, blue)
        , a(alpha) {
    }

    ColorRgba(const ColorRgba<T> &x)
        : ColorRgb<T>(x.r, x.g, x.b)
        , a(x.a) {
    }

    ColorRgba<int> operator *(int x) {
        return ColorRgba<int>(ColorRgb<T>::r * x, 
                            ColorRgb<T>::g * x, 
                            ColorRgb<T>::b * x, 
                            a * x);
    }

    ColorRgba<int> operator +(const ColorRgba<T> &x) {
        return ColorRgba<T>(ColorRgb<T>::r + (int)x.r, 
                            ColorRgb<T>::g + (int)x.g, 
                            ColorRgb<T>::b + (int)x.b, 
                            a + (int)x.a);
    }

    ColorRgba<int> operator -(const ColorRgba<T> &x) {
        return ColorRgba<T>(ColorRgb<T>::r - (int)x.r, 
                            ColorRgb<T>::g - (int)x.g, 
                            ColorRgb<T>::b - (int)x.b, 
                            a - (int)x.a);
    }

    int operator %(const ColorRgba<T> &x) {
        return ColorRgb<T>::r * (int)x.r + 
               ColorRgb<T>::g * (int)x.g + 
               ColorRgb<T>::b * (int)x.b + 
               a * (int)x.a;
    }

    bool operator ==(const ColorRgba<T> &x) {
        return ColorRgb<T>::r == x.r && ColorRgb<T>::g == x.g && 
               ColorRgb<T>::b == x.b && a == x.a;
    }

    bool operator !=(const ColorRgba<T> &x) {
        return ColorRgb<T>::r != x.r || ColorRgb<T>::g != x.g || 
               ColorRgb<T>::b != x.b || a != x.a;
    }

    void SetMin(const ColorRgba<T> &x) {
        ColorRgb<T>::SetMin(x);
        if (x.a < a) {
            a = x.a;
        }
    }

    void SetMax(const ColorRgba<T> &x) {
        ColorRgb<T>::SetMax(x);
        if (x.a > a) {
            a = x.a;
        }
    }
};


class Bitmap : public Image {
public:
    size_t GetBitmapWidth() const { return m_width; }
    size_t GetBitmapHeight() const { return m_height; }
    const unsigned char *GetRawDataConst() const { return m_data.data(); }
    unsigned char *GetRawData() { return m_data.data(); }
};


class RgbBitmap : public Bitmap {
public:
    const ColorRgb<unsigned char> *GetData() const { 
        return reinterpret_cast<const ColorRgb<unsigned char> *>(GetRawDataConst()); 
    }
    ColorRgb<unsigned char> *GetData() { 
        return reinterpret_cast<ColorRgb<unsigned char> *>(GetRawData()); 
    }
};


class RgbaBitmap : public Bitmap {
public:
    const ColorRgba<unsigned char> *GetData() const { 
        return reinterpret_cast<const ColorRgba<unsigned char> *>(GetRawDataConst()); 
    }
    ColorRgba<unsigned char> *GetData() { 
        return reinterpret_cast<ColorRgba<unsigned char> *>(GetRawData());
    }
};


class BitUtility {
public:
    static bool IsPowerOf2(uint64_t x) {
        return (x & (x - 1)) == 0;
    }

    static unsigned int RotateRight(unsigned int value, unsigned int shift) {
        if ((shift &= sizeof(value) * 8 - 1) == 0) {
            return value;
        }
        return (value >> shift) | (value << (sizeof(value) * 8 - shift));
    }
};


template<typename T>
class Interval {
public:
    T min, max;
    Interval<T> &operator|=(const T &x) {
        min.SetMin(x); 
        max.SetMax(x);
        return *this;
    }
};


//============================================================================
//
// Modulation data specifies weightings of colorA to colorB for each pixel
//
// For mode = 0
//	00: 0/8
//  01: 3/8
//  10: 5/8
//  11: 8/8
//
// For mode = 1
//  00: 0/8
//  01: 4/8
//  10: 4/8 with alpha punchthrough
//  11: 8/8
//
// For colorIsOpaque=0
//  3 bits A
//  4 bits R
//  4 bits G
//  3/4 bits B
//
// For colorIsOpaque=1
//  5 bits R
//  5 bits G
//  4/5 bits B
//
//============================================================================


struct PvrTcPacket
{
    unsigned modulationData;
    unsigned usePunchthroughAlpha : 1;
    unsigned colorA               : 14;
    unsigned colorAIsOpaque       : 1;
    unsigned colorB               : 15;
    unsigned colorBIsOpaque       : 1;
    
    ColorRgba<int> GetColorRgbaA() const;
    ColorRgba<int> GetColorRgbaB() const;
    void SetColorA(const ColorRgb<unsigned char>& c);
    void SetColorB(const ColorRgb<unsigned char>& c);
    void SetColorA(const ColorRgba<unsigned char>& c);
    void SetColorB(const ColorRgba<unsigned char>& c);
};


//============================================================================

//============================================================================
inline ColorRgba<int> GetColorRgbGen(unsigned inColor, unsigned rs, unsigned rm,
    unsigned gs, unsigned gm, unsigned bm, const uint8_t rscale[], const uint8_t gscale[], const uint8_t bscale[], int alpha = 255)
{
    unsigned char r = (inColor >> rs) & rm;
    unsigned char g = (inColor >> gs) & gm;
    unsigned char b = inColor & bm;
    return ColorRgba<int>(rscale[r], gscale[g], bscale[b], alpha);
}

ColorRgba<int> PvrTcPacket::GetColorRgbaA() const
{
	if (colorAIsOpaque)
        return GetColorRgbGen(colorA, 9, 0xff, 4, 0x1f, 0xf, BITSCALE_5_TO_8, BITSCALE_5_TO_8, BITSCALE_4_TO_8);
    unsigned char a = colorA >> 11 & 7;
    return GetColorRgbGen(colorA, 7, 0xf, 3, 0xf, 0x7, BITSCALE_4_TO_8, BITSCALE_4_TO_8, BITSCALE_3_TO_8, BITSCALE_3_TO_8[a]);
}

ColorRgba<int> PvrTcPacket::GetColorRgbaB() const
{
	if (colorBIsOpaque)
        return GetColorRgbGen(colorB, 10, 0xff, 5, 0x1f, 0x1f, BITSCALE_5_TO_8, BITSCALE_5_TO_8, BITSCALE_5_TO_8);
	unsigned char a = colorB >> 12 & 7;
    return GetColorRgbGen(colorB, 8, 0xf, 4, 0xf, 0xf, BITSCALE_4_TO_8, BITSCALE_4_TO_8, BITSCALE_4_TO_8, BITSCALE_3_TO_8[a]);
}

//============================================================================

void PvrTcPacket::SetColorA(const ColorRgb<unsigned char>& c)
{
	int r = BITSCALE_8_TO_5_FLOOR[c.r];
	int g = BITSCALE_8_TO_5_FLOOR[c.g];
	int b = BITSCALE_8_TO_4_FLOOR[c.b];
	colorA = r<<9 | g<<4 | b;
	colorAIsOpaque = true;
}

void PvrTcPacket::SetColorB(const ColorRgb<unsigned char>& c)
{
	int r = BITSCALE_8_TO_5_CEIL[c.r];
	int g = BITSCALE_8_TO_5_CEIL[c.g];
	int b = BITSCALE_8_TO_5_CEIL[c.b];
	colorB = r<<10 | g<<5 | b;
	colorBIsOpaque = true;
}

void PvrTcPacket::SetColorA(const ColorRgba<unsigned char>& c)
{
	int a = BITSCALE_8_TO_3_FLOOR[c.a];
	if(a == 7)
	{
        SetColorA((const ColorRgb<unsigned char>&)c);
        /*
		int r = BITSCALE_8_TO_5_FLOOR[c.r];
		int g = BITSCALE_8_TO_5_FLOOR[c.g];
		int b = BITSCALE_8_TO_4_FLOOR[c.b];
		colorA = r<<9 | g<<4 | b;
		colorAIsOpaque = true;
        */
	}
	else
	{
		int r = BITSCALE_8_TO_4_FLOOR[c.r];
		int g = BITSCALE_8_TO_4_FLOOR[c.g];
		int b = BITSCALE_8_TO_3_FLOOR[c.b];
		colorA = a<<11 | r<<7 | g<<3 | b;
		colorAIsOpaque = false;
	}
}

void PvrTcPacket::SetColorB(const ColorRgba<unsigned char>& c)
{
	int a = BITSCALE_8_TO_3_CEIL[c.a];
	if(a == 7)
	{
        SetColorB((const ColorRgb<unsigned char>&)c);
        /*
		int r = BITSCALE_8_TO_5_CEIL[c.r];
		int g = BITSCALE_8_TO_5_CEIL[c.g];
		int b = BITSCALE_8_TO_5_CEIL[c.b];
		colorB = r<<10 | g<<5 | b;
		colorBIsOpaque = true;
        */
	}
	else
	{
		int r = BITSCALE_8_TO_4_CEIL[c.r];
		int g = BITSCALE_8_TO_4_CEIL[c.g];
		int b = BITSCALE_8_TO_4_CEIL[c.b];
		colorB = a<<12 | r<<8 | g<<4 | b;
		colorBIsOpaque = false;
	}
}

//============================================================================
/*
static const unsigned char MODULATION_LUT[16] =
{
	0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3
};
*/

//============================================================================

inline unsigned GetMortonNumber(int x, int y)
{
	return MORTON_TABLE[x >> 8] << 17 | MORTON_TABLE[y >> 8] << 16 | MORTON_TABLE[x & 0xFF] << 1 | MORTON_TABLE[y & 0xFF];
}

//============================================================================

typedef Interval<ColorRgb<unsigned char>> ColorRgbBoundingBox;
typedef Interval<ColorRgba<unsigned char>> ColorRgbaBoundingBox;

template <typename BoxType, typename BitmapType>
static void CalculateBoundingBox(BoxType& cbb, const BitmapType& bitmap, int blockX, int blockY)
{
	size_t size = bitmap.GetBitmapWidth();
	auto data = bitmap.GetData() + blockY * 4 * size + blockX * 4;
	
	cbb.min = data[0];
	cbb.max = data[0];
	cbb |= data[1];
	cbb |= data[2];
	cbb |= data[3];
	
	cbb |= data[size];
	cbb |= data[size+1];
	cbb |= data[size+2];
	cbb |= data[size+3];

	cbb |= data[2*size];
	cbb |= data[2*size+1];
	cbb |= data[2*size+2];
	cbb |= data[2*size+3];

	cbb |= data[3*size];
	cbb |= data[3*size+1];
	cbb |= data[3*size+2];
	cbb |= data[3*size+3];
}


template <typename OutputType>
void GetColorAColorB(const PvrTcPacket* packets, const unsigned char factor[4], int blockMask, int px, int x, int y0, int y1, OutputType& colorA, OutputType& colorB)
{
    const int xOffset = (px < 2) ? -1 : 0;
    const int x0 = (x + xOffset) & blockMask;
    const int x1 = (x0+1) & blockMask;

    const PvrTcPacket* p0 = packets + GetMortonNumber(x0, y0);
    const PvrTcPacket* p1 = packets + GetMortonNumber(x1, y0);
    const PvrTcPacket* p2 = packets + GetMortonNumber(x0, y1);
    const PvrTcPacket* p3 = packets + GetMortonNumber(x1, y1);

    colorA = p0->GetColorRgbaA() * factor[0] +
      p1->GetColorRgbaA() * factor[1] +
      p2->GetColorRgbaA() * factor[2] +
      p3->GetColorRgbaA() * factor[3];

    colorB = p0->GetColorRgbaB() * factor[0] +
      p1->GetColorRgbaB() * factor[1] +
      p2->GetColorRgbaB() * factor[2] +
      p3->GetColorRgbaB() * factor[3];
}


template <typename OutputType, typename BoxType, typename BitmapType>
void Encode4Bpp(void* result, const BitmapType& bitmap)
{
	assert(bitmap.GetBitmapWidth() == bitmap.GetBitmapHeight());
	assert(BitUtility::IsPowerOf2(bitmap.GetBitmapWidth()));
	const size_t size = bitmap.GetBitmapWidth();
	const int blocks = int(size / 4);
	const int blockMask = int(blocks-1);
	
	PvrTcPacket* packets = static_cast<PvrTcPacket*>(result);

	for(int y = 0; y < blocks; ++y)
	{
		for(int x = 0; x < blocks; ++x)
		{
			BoxType cbb;
			CalculateBoundingBox(cbb, bitmap, x, y);
			PvrTcPacket* packet = packets + GetMortonNumber(x, y);
			packet->usePunchthroughAlpha = 0;
			packet->SetColorA(cbb.min);
			packet->SetColorB(cbb.max);
		}
	}
	
	for(int y = 0; y < blocks; ++y)
	{
		for(int x = 0; x < blocks; ++x)
		{
			const unsigned char (*factor)[4] = BILINEAR_FACTORS;
			auto data = bitmap.GetData() + y * 4 * size + x * 4;

			uint32_t modulationData = 0;

			for(int py = 0; py < 4; ++py)
			{
				const int yOffset = (py < 2) ? -1 : 0;
				const int y0 = (y + yOffset) & blockMask;
				const int y1 = (y0+1) & blockMask;

				for(int px = 0; px < 4; ++px)
				{
                    OutputType ca, cb;
                    GetColorAColorB(packets, *factor, blockMask, px, x, y0, y1, ca, cb);

					auto pixel = data[py*size + px];
                    auto pixel16 = pixel * 16;
					OutputType d = cb - ca;
					OutputType p = pixel16;
					OutputType v = p - ca;
					
					// PVRTC uses weightings of 0, 3/8, 5/8 and 1
					// The boundaries for these are 3/16, 1/2 (=8/16), 13/16
					int projection = (v % d) * 16;
					int lengthSquared = d % d;
					if(projection > 3*lengthSquared) modulationData++;
					if(projection > 8*lengthSquared) modulationData++;
					if(projection > 13*lengthSquared) modulationData++;
					
					modulationData = BitUtility::RotateRight(modulationData, 2);
					
					factor++;
				}
			}

			PvrTcPacket* packet = packets + GetMortonNumber(x, y);
			packet->modulationData = modulationData;
		}
	}
}

void EncodeRgb4Bpp(void *result, const RgbBitmap& bitmap)
{
  Encode4Bpp< ColorRgb<int>, ColorRgbBoundingBox >(result, bitmap);
}

void EncodeRgb4Bpp(void *result, const RgbaBitmap& bitmap)
{
  Encode4Bpp< ColorRgb<int>, ColorRgbBoundingBox >(result, bitmap);
}

void EncodeRgba4Bpp(void *result, const RgbaBitmap& bitmap)
{
  Encode4Bpp< ColorRgba<int>, ColorRgbaBoundingBox, const RgbaBitmap& >(result, bitmap);
}

//============================================================================

template <typename OutputType>
void Decode4Bpp(OutputType* result, size_t dim, const void* data)
{
	const int blocks = int(dim / 4);
	const int blockMask = blocks-1;
    const PvrTcPacket* packets = static_cast<const PvrTcPacket*>(data);
    
    for(int y = 0; y < blocks; ++y)
    {
        for(int x = 0; x < blocks; ++x)
        {
            const PvrTcPacket* packet = packets + GetMortonNumber(x, y);
            
            unsigned mod = packet->modulationData;
            const unsigned char (*weights)[4] = WEIGHTS + 4*packet->usePunchthroughAlpha;
            const unsigned char (*factor)[4] = BILINEAR_FACTORS;
			
			for(int py = 0; py < 4; ++py)
			{
				const int yOffset = (py < 2) ? -1 : 0;
				const int y0 = (y + yOffset) & blockMask;
				const int y1 = (y0+1) & blockMask;
				
				for(int px = 0; px < 4; ++px)
				{
                    ColorRgba<int> ca, cb;
                    GetColorAColorB(packets, *factor, blockMask, px, x, y0, y1, ca, cb);
					
					const unsigned char* w = weights[mod&3];
                    ColorRgba<unsigned char> c;
					c.r = (ca.r * w[0] + cb.r * w[1]) >> 7;
					c.g = (ca.g * w[0] + cb.g * w[1]) >> 7;
					c.b = (ca.b * w[0] + cb.b * w[1]) >> 7;
					c.a = (ca.a * w[2] + cb.a * w[3]) >> 7;
					
					result[(py+y*4)*dim + (px+x*4)] = c;
					mod >>= 2;
					factor++;
				}
			}
        }
    }
}


void DecodeRgb4Bpp(ColorRgb<unsigned char>* result, size_t dim, const void* data)
{
    Decode4Bpp(result, dim, data);
}


void DecodeRgba4Bpp(ColorRgba<unsigned char>* result, size_t dim, const void* data)
{
    Decode4Bpp(result, dim, data);
}


} // end PvrImage namespace 

//============================================================================

bool ConvertImage(const Image& inImage, Image& outImage, ImageType outputFormat)
{
  using namespace PvrImage;

  if ( inImage.m_type == outputFormat )
  {
    Log(LL_Debug, "warning: same format, copying without conversion");
    outImage = inImage;
    return true;
  }

  if ( inImage.m_width != inImage.m_height )
  {
    Log(LL_Debug, "non power of 2, or non square dimensions");
    return false;
  }

  outImage.m_type   = outputFormat;
  outImage.m_width  = inImage.m_width;
  outImage.m_height = inImage.m_height;
  const size_t siz  = inImage.m_width * inImage.m_height;

  // Encoding
  if (inImage.m_type == RAW_RGB_24BPP) {
    if (outputFormat == PVRTC_RGB_4BPPV1 || outputFormat == PVRTC_RGBA_4BPPV1) {
      if (outputFormat == PVRTC_RGBA_4BPPV1)
        Log(LL_Debug, "Warning, source image has no alpha, no alpha in output");
      outImage.m_data.resize(siz / 2);
      EncodeRgb4Bpp(outImage.m_data.data(), static_cast<const RgbBitmap&>(inImage));
      return true;
    }
  } else if (inImage.m_type == RAW_RGBA_32BPP) {
    if (outputFormat == PVRTC_RGB_4BPPV1) {
      Log(LL_Debug, "Warning, input may contain alpha which is being dropped in output");
      outImage.m_data.resize(siz / 2);
      EncodeRgb4Bpp(outImage.m_data.data(), static_cast<const RgbaBitmap&>(inImage));
      return true;
    } else if (outputFormat == PVRTC_RGBA_4BPPV1) {
      Log(LL_Debug, "here!");
      outImage.m_data.resize(siz / 2);
      EncodeRgba4Bpp(outImage.m_data.data(), static_cast<const RgbaBitmap&>(inImage));
      return true;
    }

  // Decoding
  } else if (inImage.m_type == PVRTC_RGB_4BPPV1) {
    if (outputFormat == RAW_RGB_24BPP) {
      outImage.m_data.resize(siz * 3);
      DecodeRgb4Bpp(reinterpret_cast<ColorRgb<unsigned char>*>(outImage.m_data.data()), inImage.m_width, inImage.m_data.data());
      return true;
    } else if (outputFormat == RAW_RGBA_32BPP) {
      Log(LL_Debug, "Warning, source input has no alpha, no alpha in output");
      outImage.m_data.resize(siz * 4);
      DecodeRgba4Bpp(reinterpret_cast<ColorRgba<unsigned char>*>(outImage.m_data.data()), inImage.m_width, inImage.m_data.data());
      return true;
    }
  } else if (inImage.m_type == PVRTC_RGBA_4BPPV1) {
    if (outputFormat == RAW_RGB_24BPP) {
      Log(LL_Debug, "Warning, input may contain alpha which is being dropped in output");
      outImage.m_data.resize(siz * 3);
      DecodeRgb4Bpp(reinterpret_cast<ColorRgb<unsigned char>*>(outImage.m_data.data()), inImage.m_width, inImage.m_data.data());
      return true;
    } else if (outputFormat == RAW_RGBA_32BPP) {
      outImage.m_data.resize(siz * 4);
      DecodeRgba4Bpp(reinterpret_cast<ColorRgba<unsigned char>*>(outImage.m_data.data()), inImage.m_width, inImage.m_data.data());
      return true;
    }
  }

  Log(LL_Error, "unsupported convert formats");
  return false;
}




#if 0


// Unused


class AlphaBitmap : public Bitmap {
public:
    AlphaBitmap(int w, int h) : Bitmap(w, h, 1) {} 
};

static void EncodeAlpha2Bpp(void* result, const AlphaBitmap& bitmap);
static void EncodeAlpha4Bpp(void* result, const AlphaBitmap& bitmap);


void EncodeAlpha2Bpp(void* result, const AlphaBitmap& bitmap)
{
	int size = bitmap.GetBitmapWidth();
	assert(size == bitmap.GetBitmapHeight());
	assert(BitUtility::IsPowerOf2(size));
	
	// Blocks in each dimension.
	int xBlocks = size/8;
	int yBlocks = size/4;
	
	const unsigned char* bitmapData = bitmap.GetRawDataConst();
	
	PvrTcPacket* packets = static_cast<PvrTcPacket*>(result);
	for(int y = 0; y < yBlocks; ++y)
	{
		for(int x = 0; x < xBlocks; ++x)
		{
			PvrTcPacket* packet = packets + GetMortonNumber(x, y);
			packet->usePunchthroughAlpha = 0;
			packet->colorAIsOpaque = 0;
			packet->colorA = 0x7ff;		// White, with 0 alpha
			packet->colorBIsOpaque = 1;
			packet->colorB = 0x7fff;	// White with full alpha
			
			const unsigned char* blockBitmapData = &bitmapData[y*4*size + x*8];
			
			uint32_t modulationData = 0;
			for(int py = 0; py < 4; ++py)
			{
				const unsigned char* rowBitmapData = blockBitmapData;
				for(int px = 0; px < 8; ++px)
				{
					unsigned char pixel = *rowBitmapData++;
					modulationData = BitUtility::RotateRight(modulationData | (pixel >> 7), 1);
				}
				blockBitmapData += size;
			}
			packet->modulationData = modulationData;
		}
	}
}

void EncodeAlpha4Bpp(void* result, const AlphaBitmap& bitmap)
{
	int size = bitmap.GetBitmapWidth();
	assert(size == bitmap.GetBitmapHeight());
	assert(BitUtility::IsPowerOf2(size));
	
	// Blocks in each dimension.
	int blocks = size/4;
	
	const unsigned char* bitmapData = bitmap.GetRawDataConst();
	
	PvrTcPacket* packets = static_cast<PvrTcPacket*>(result);
	for(int y = 0; y < blocks; ++y)
	{
		for(int x = 0; x < blocks; ++x)
		{
			PvrTcPacket* packet = packets + GetMortonNumber(x, y);
			packet->usePunchthroughAlpha = 0;
			packet->colorAIsOpaque = 0;
			packet->colorA = 0x7ff;		// White, with 0 alpha
			packet->colorBIsOpaque = 1;
			packet->colorB = 0x7fff;	// White with full alpha

			const unsigned char* blockBitmapData = &bitmapData[(y*size + x)*4];
			
			uint32_t modulationData = 0;
			for(int py = 0; py < 4; ++py)
			{
				const unsigned char* rowBitmapData = blockBitmapData;
				for(int px = 0; px < 4; ++px)
				{
					unsigned char pixel = *rowBitmapData++;
					modulationData = BitUtility::RotateRight(modulationData | MODULATION_LUT[pixel>>4], 2);
				}
				blockBitmapData += size;
			}
			packet->modulationData = modulationData;
		}
	}
}


#endif


