git.cworth.org Git - vogl/blob - src/voglcore/vogl_rg_etc1.cpp

   1 /**************************************************************************
   2  *
   3  * Copyright 2013-2014 RAD Game Tools and Valve Software
   4  * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
   5  * All Rights Reserved.
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy
   8  * of this software and associated documentation files (the "Software"), to deal
   9  * in the Software without restriction, including without limitation the rights
  10  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  11  * copies of the Software, and to permit persons to whom the Software is
  12  * furnished to do so, subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included in
  15  * all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  20  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  22  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  23  * THE SOFTWARE.
  24  *
  25  **************************************************************************/
  26
  27 // File: rg_etc1.cpp - Fast, high quality ETC1 block packer/unpacker - Rich Geldreich <richgel99@gmail.com>
  28 // Please see ZLIB license at the end of rg_etc1.h.
  29 //
  30 // For more information Ericsson Texture Compression (ETC/ETC1), see:
  31 // http://www.khronos.org/registry/gles/extensions/OES/OES_compressed_ETC1_RGB8_texture.txt
  32 //
  33 // v1.03 - 5/12/13 - Initial public release
  34 #include "vogl_core.h"
  35 #include "vogl_rg_etc1.h"
  36
  37 #include <stdlib.h>
  38 #include <memory.h>
  39 #include <assert.h>
  40 //#include <stdio.h>
  41 #include <math.h>
  42
  43 #if defined(_MSC_VER)
  44 #pragma warning(disable : 4201) //  nonstandard extension used : nameless struct/union
  45 #endif
  46
  47 #if defined(_DEBUG) || defined(DEBUG)
  48 #define RG_ETC1_BUILD_DEBUG
  49 #endif
  50
  51 #define RG_ETC1_ASSERT VOGL_ASSERT
  52
  53 namespace vogl
  54 {
  55
  56     namespace rg_etc1
  57     {
  58         typedef unsigned char uint8;
  59         typedef unsigned short uint16;
  60         typedef unsigned int uint;
  61         typedef unsigned int uint32;
  62         typedef long long int64_t;
  63         typedef unsigned long long uint64_t;
  64
  65         const uint32 cUINT32_MAX = 0xFFFFFFFFU;
  66         const uint64_t cUINT64_MAX = 0xFFFFFFFFFFFFFFFFULL; //0xFFFFFFFFFFFFFFFFui64;
  67
  68         template <typename T>
  69         inline T minimum(T a, T b)
  70         {
  71             return (a < b) ? a : b;
  72         }
  73         template <typename T>
  74         inline T minimum(T a, T b, T c)
  75         {
  76             return minimum(minimum(a, b), c);
  77         }
  78         template <typename T>
  79         inline T maximum(T a, T b)
  80         {
  81             return (a > b) ? a : b;
  82         }
  83         template <typename T>
  84         inline T maximum(T a, T b, T c)
  85         {
  86             return maximum(maximum(a, b), c);
  87         }
  88         template <typename T>
  89         inline T clamp(T value, T low, T high)
  90         {
  91             return (value < low) ? low : ((value > high) ? high : value);
  92         }
  93         template <typename T>
  94         inline T square(T value)
  95         {
  96             return value * value;
  97         }
  98         template <typename T>
  99         inline void zero_object(T &obj)
 100         {
 101             memset((void *)&obj, 0, sizeof(obj));
 102         }
 103         template <typename T>
 104         inline void zero_this(T *pObj)
 105         {
 106             memset((void *)pObj, 0, sizeof(*pObj));
 107         }
 108
 109         template <class T, size_t N>
 110         T decay_array_to_subtype(T (&a)[N]);
 111
 112 #define RG_ETC1_ARRAY_SIZE(X) (sizeof(X) / sizeof(decay_array_to_subtype(X)))
 113
 114         enum eNoClamp
 115         {
 116             cNoClamp
 117         };
 118
 119         struct color_quad_u8
 120         {
 121             static inline int clamp(int v)
 122             {
 123                 if (v & 0xFFFFFF00U)
 124                     v = (~(static_cast<int>(v) >> 31)) & 0xFF;
 125                 return v;
 126             }
 127
 128             struct component_traits
 129             {
 130                 enum
 131                 {
 132                     cSigned = false,
 133                     cFloat = false,
 134                     cMin = 0U,
 135                     cMax = 255U
 136                 };
 137             };
 138
 139         public:
 140             typedef unsigned char component_t;
 141             typedef int parameter_t;
 142
 143             enum
 144             {
 145                 cNumComps = 4
 146             };
 147
 148             union
 149             {
 150                 struct
 151                 {
 152                     component_t r;
 153                     component_t g;
 154                     component_t b;
 155                     component_t a;
 156                 };
 157
 158                 component_t c[cNumComps];
 159
 160                 uint32 m_u32;
 161             };
 162
 163             inline color_quad_u8()
 164             {
 165             }
 166
 167             inline color_quad_u8(const color_quad_u8 &other)
 168                 : m_u32(other.m_u32)
 169             {
 170             }
 171
 172             explicit inline color_quad_u8(parameter_t y, parameter_t alpha = component_traits::cMax)
 173             {
 174                 set(y, alpha);
 175             }
 176
 177             inline color_quad_u8(parameter_t red, parameter_t green, parameter_t blue, parameter_t alpha = component_traits::cMax)
 178             {
 179                 set(red, green, blue, alpha);
 180             }
 181
 182             explicit inline color_quad_u8(eNoClamp, parameter_t y, parameter_t alpha = component_traits::cMax)
 183             {
 184                 set_noclamp_y_alpha(y, alpha);
 185             }
 186
 187             inline color_quad_u8(eNoClamp, parameter_t red, parameter_t green, parameter_t blue, parameter_t alpha = component_traits::cMax)
 188             {
 189                 set_noclamp_rgba(red, green, blue, alpha);
 190             }
 191
 192             inline void clear()
 193             {
 194                 m_u32 = 0;
 195             }
 196
 197             inline color_quad_u8 &operator=(const color_quad_u8 &other)
 198             {
 199                 m_u32 = other.m_u32;
 200                 return *this;
 201             }
 202
 203             inline color_quad_u8 &set_rgb(const color_quad_u8 &other)
 204             {
 205                 r = other.r;
 206                 g = other.g;
 207                 b = other.b;
 208                 return *this;
 209             }
 210
 211             inline color_quad_u8 &operator=(parameter_t y)
 212             {
 213                 set(y, component_traits::cMax);
 214                 return *this;
 215             }
 216
 217             inline color_quad_u8 &set(parameter_t y, parameter_t alpha = component_traits::cMax)
 218             {
 219                 y = clamp(y);
 220                 alpha = clamp(alpha);
 221                 r = static_cast<component_t>(y);
 222                 g = static_cast<component_t>(y);
 223                 b = static_cast<component_t>(y);
 224                 a = static_cast<component_t>(alpha);
 225                 return *this;
 226             }
 227
 228             inline color_quad_u8 &set_noclamp_y_alpha(parameter_t y, parameter_t alpha = component_traits::cMax)
 229             {
 230                 RG_ETC1_ASSERT((y >= component_traits::cMin) && (y <= component_traits::cMax));
 231                 RG_ETC1_ASSERT((alpha >= component_traits::cMin) && (alpha <= component_traits::cMax));
 232
 233                 r = static_cast<component_t>(y);
 234                 g = static_cast<component_t>(y);
 235                 b = static_cast<component_t>(y);
 236                 a = static_cast<component_t>(alpha);
 237                 return *this;
 238             }
 239
 240             inline color_quad_u8 &set(parameter_t red, parameter_t green, parameter_t blue, parameter_t alpha = component_traits::cMax)
 241             {
 242                 r = static_cast<component_t>(clamp(red));
 243                 g = static_cast<component_t>(clamp(green));
 244                 b = static_cast<component_t>(clamp(blue));
 245                 a = static_cast<component_t>(clamp(alpha));
 246                 return *this;
 247             }
 248
 249             inline color_quad_u8 &set_noclamp_rgba(parameter_t red, parameter_t green, parameter_t blue, parameter_t alpha)
 250             {
 251                 RG_ETC1_ASSERT((red >= component_traits::cMin) && (red <= component_traits::cMax));
 252                 RG_ETC1_ASSERT((green >= component_traits::cMin) && (green <= component_traits::cMax));
 253                 RG_ETC1_ASSERT((blue >= component_traits::cMin) && (blue <= component_traits::cMax));
 254                 RG_ETC1_ASSERT((alpha >= component_traits::cMin) && (alpha <= component_traits::cMax));
 255
 256                 r = static_cast<component_t>(red);
 257                 g = static_cast<component_t>(green);
 258                 b = static_cast<component_t>(blue);
 259                 a = static_cast<component_t>(alpha);
 260                 return *this;
 261             }
 262
 263             inline color_quad_u8 &set_noclamp_rgb(parameter_t red, parameter_t green, parameter_t blue)
 264             {
 265                 RG_ETC1_ASSERT((red >= component_traits::cMin) && (red <= component_traits::cMax));
 266                 RG_ETC1_ASSERT((green >= component_traits::cMin) && (green <= component_traits::cMax));
 267                 RG_ETC1_ASSERT((blue >= component_traits::cMin) && (blue <= component_traits::cMax));
 268
 269                 r = static_cast<component_t>(red);
 270                 g = static_cast<component_t>(green);
 271                 b = static_cast<component_t>(blue);
 272                 return *this;
 273             }
 274
 275             static inline parameter_t get_min_comp()
 276             {
 277                 return component_traits::cMin;
 278             }
 279             static inline parameter_t get_max_comp()
 280             {
 281                 return component_traits::cMax;
 282             }
 283             static inline bool get_comps_are_signed()
 284             {
 285                 return component_traits::cSigned;
 286             }
 287
 288             inline component_t operator[](uint i) const
 289             {
 290                 RG_ETC1_ASSERT(i < cNumComps);
 291                 return c[i];
 292             }
 293             inline component_t &operator[](uint i)
 294             {
 295                 RG_ETC1_ASSERT(i < cNumComps);
 296                 return c[i];
 297             }
 298
 299             inline color_quad_u8 &set_component(uint i, parameter_t f)
 300             {
 301                 RG_ETC1_ASSERT(i < cNumComps);
 302
 303                 c[i] = static_cast<component_t>(clamp(f));
 304
 305                 return *this;
 306             }
 307
 308             inline color_quad_u8 &set_grayscale(parameter_t l)
 309             {
 310                 component_t x = static_cast<component_t>(clamp(l));
 311                 c[0] = x;
 312                 c[1] = x;
 313                 c[2] = x;
 314                 return *this;
 315             }
 316
 317             inline color_quad_u8 &clamp(const color_quad_u8 &l, const color_quad_u8 &h)
 318             {
 319                 for (uint i = 0; i < cNumComps; i++)
 320                     c[i] = static_cast<component_t>(rg_etc1::clamp<parameter_t>(c[i], l[i], h[i]));
 321                 return *this;
 322             }
 323
 324             inline color_quad_u8 &clamp(parameter_t l, parameter_t h)
 325             {
 326                 for (uint i = 0; i < cNumComps; i++)
 327                     c[i] = static_cast<component_t>(rg_etc1::clamp<parameter_t>(c[i], l, h));
 328                 return *this;
 329             }
 330
 331             // Returns CCIR 601 luma (consistent with color_utils::RGB_To_Y).
 332             inline parameter_t get_luma() const
 333             {
 334                 return static_cast<parameter_t>((19595U * r + 38470U * g + 7471U * b + 32768U) >> 16U);
 335             }
 336
 337             // Returns REC 709 luma.
 338             inline parameter_t get_luma_rec709() const
 339             {
 340                 return static_cast<parameter_t>((13938U * r + 46869U * g + 4729U * b + 32768U) >> 16U);
 341             }
 342
 343             inline uint squared_distance_rgb(const color_quad_u8 &c) const
 344             {
 345                 return rg_etc1::square(r - c.r) + rg_etc1::square(g - c.g) + rg_etc1::square(b - c.b);
 346             }
 347
 348             inline uint squared_distance_rgba(const color_quad_u8 &c) const
 349             {
 350                 return rg_etc1::square(r - c.r) + rg_etc1::square(g - c.g) + rg_etc1::square(b - c.b) + rg_etc1::square(a - c.a);
 351             }
 352
 353             inline bool rgb_equals(const color_quad_u8 &rhs) const
 354             {
 355                 return (r == rhs.r) && (g == rhs.g) && (b == rhs.b);
 356             }
 357
 358             inline bool operator==(const color_quad_u8 &rhs) const
 359             {
 360                 return m_u32 == rhs.m_u32;
 361             }
 362
 363             color_quad_u8 &operator+=(const color_quad_u8 &other)
 364             {
 365                 for (uint i = 0; i < 4; i++)
 366                     c[i] = static_cast<component_t>(clamp(c[i] + other.c[i]));
 367                 return *this;
 368             }
 369
 370             color_quad_u8 &operator-=(const color_quad_u8 &other)
 371             {
 372                 for (uint i = 0; i < 4; i++)
 373                     c[i] = static_cast<component_t>(clamp(c[i] - other.c[i]));
 374                 return *this;
 375             }
 376
 377             friend color_quad_u8 operator+(const color_quad_u8 &lhs, const color_quad_u8 &rhs)
 378             {
 379                 color_quad_u8 result(lhs);
 380                 result += rhs;
 381                 return result;
 382             }
 383
 384             friend color_quad_u8 operator-(const color_quad_u8 &lhs, const color_quad_u8 &rhs)
 385             {
 386                 color_quad_u8 result(lhs);
 387                 result -= rhs;
 388                 return result;
 389             }
 390         }; // class color_quad_u8
 391
 392         struct vec3F
 393         {
 394             float m_s[3];
 395
 396             inline vec3F()
 397             {
 398             }
 399             inline vec3F(float s)
 400             {
 401                 m_s[0] = s;
 402                 m_s[1] = s;
 403                 m_s[2] = s;
 404             }
 405             inline vec3F(float x, float y, float z)
 406             {
 407                 m_s[0] = x;
 408                 m_s[1] = y;
 409                 m_s[2] = z;
 410             }
 411
 412             inline float operator[](uint i) const
 413             {
 414                 RG_ETC1_ASSERT(i < 3);
 415                 return m_s[i];
 416             }
 417
 418             inline vec3F &operator+=(const vec3F &other)
 419             {
 420                 for (uint i = 0; i < 3; i++)
 421                     m_s[i] += other.m_s[i];
 422                 return *this;
 423             }
 424
 425             inline vec3F &operator*=(float s)
 426             {
 427                 for (uint i = 0; i < 3; i++)
 428                     m_s[i] *= s;
 429                 return *this;
 430             }
 431         };
 432
 433         enum etc_constants
 434         {
 435             cETC1BytesPerBlock = 8U,
 436             cETC1SelectorBits = 2U,
 437             cETC1SelectorValues = 1U << cETC1SelectorBits,
 438             cETC1SelectorMask = cETC1SelectorValues - 1U,
 439             cETC1BlockShift = 2U,
 440             cETC1BlockSize = 1U << cETC1BlockShift,
 441             cETC1LSBSelectorIndicesBitOffset = 0,
 442             cETC1MSBSelectorIndicesBitOffset = 16,
 443             cETC1FlipBitOffset = 32,
 444             cETC1DiffBitOffset = 33,
 445             cETC1IntenModifierNumBits = 3,
 446             cETC1IntenModifierValues = 1 << cETC1IntenModifierNumBits,
 447             cETC1RightIntenModifierTableBitOffset = 34,
 448             cETC1LeftIntenModifierTableBitOffset = 37,
 449
 450             // Base+Delta encoding (5 bit bases, 3 bit delta)
 451             cETC1BaseColorCompNumBits = 5,
 452             cETC1BaseColorCompMax = 1 << cETC1BaseColorCompNumBits,
 453             cETC1DeltaColorCompNumBits = 3,
 454             cETC1DeltaColorComp = 1 << cETC1DeltaColorCompNumBits,
 455             cETC1DeltaColorCompMax = 1 << cETC1DeltaColorCompNumBits,
 456             cETC1BaseColor5RBitOffset = 59,
 457             cETC1BaseColor5GBitOffset = 51,
 458             cETC1BaseColor5BBitOffset = 43,
 459             cETC1DeltaColor3RBitOffset = 56,
 460             cETC1DeltaColor3GBitOffset = 48,
 461             cETC1DeltaColor3BBitOffset = 40,
 462
 463             // Absolute (non-delta) encoding (two 4-bit per component bases)
 464             cETC1AbsColorCompNumBits = 4,
 465             cETC1AbsColorCompMax = 1 << cETC1AbsColorCompNumBits,
 466             cETC1AbsColor4R1BitOffset = 60,
 467             cETC1AbsColor4G1BitOffset = 52,
 468             cETC1AbsColor4B1BitOffset = 44,
 469             cETC1AbsColor4R2BitOffset = 56,
 470             cETC1AbsColor4G2BitOffset = 48,
 471             cETC1AbsColor4B2BitOffset = 40,
 472             cETC1ColorDeltaMin = -4,
 473             cETC1ColorDeltaMax = 3,
 474
 475             // Delta3:
 476             // 0   1   2   3   4   5   6   7
 477             // 000 001 010 011 100 101 110 111
 478             // 0   1   2   3   -4  -3  -2  -1
 479         };
 480
 481         static uint8 g_quant5_tab[256 + 16];
 482
 483         static const int g_etc1_inten_tables[cETC1IntenModifierValues][cETC1SelectorValues] =
 484             {
 485                 { -8, -2, 2, 8 }, { -17, -5, 5, 17 }, { -29, -9, 9, 29 }, { -42, -13, 13, 42 },
 486                 { -60, -18, 18, 60 }, { -80, -24, 24, 80 }, { -106, -33, 33, 106 }, { -183, -47, 47, 183 }
 487             };
 488
 489         static const uint8 g_etc1_to_selector_index[cETC1SelectorValues] = { 2, 3, 1, 0 };
 490         static const uint8 g_selector_index_to_etc1[cETC1SelectorValues] = { 3, 2, 0, 1 };
 491
 492         // Given an ETC1 diff/inten_table/selector, and an 8-bit desired color, this table encodes the best packed_color in the low byte, and the abs error in the high byte.
 493         static uint16 g_etc1_inverse_lookup[2 * 8 * 4][256]; // [diff/inten_table/selector][desired_color]
 494
 495         // g_color8_to_etc_block_config[color][table_index] = Supplies for each 8-bit color value a list of packed ETC1 diff/intensity table/selectors/packed_colors that map to that color.
 496         // To pack: diff | (inten << 1) | (selector << 4) | (packed_c << 8)
 497         static const uint16 g_color8_to_etc_block_config_0_255[2][33] =
 498             {
 499                 { 0x0000, 0x0010, 0x0002, 0x0012, 0x0004, 0x0014, 0x0006, 0x0016, 0x0008, 0x0018, 0x000A, 0x001A, 0x000C, 0x001C, 0x000E, 0x001E,
 500                   0x0001, 0x0011, 0x0003, 0x0013, 0x0005, 0x0015, 0x0007, 0x0017, 0x0009, 0x0019, 0x000B, 0x001B, 0x000D, 0x001D, 0x000F, 0x001F, 0xFFFF },
 501                 { 0x0F20, 0x0F30, 0x0E32, 0x0F22, 0x0E34, 0x0F24, 0x0D36, 0x0F26, 0x0C38, 0x0E28, 0x0B3A, 0x0E2A, 0x093C, 0x0E2C, 0x053E, 0x0D2E,
 502                   0x1E31, 0x1F21, 0x1D33, 0x1F23, 0x1C35, 0x1E25, 0x1A37, 0x1E27, 0x1839, 0x1D29, 0x163B, 0x1C2B, 0x133D, 0x1B2D, 0x093F, 0x1A2F, 0xFFFF },
 503             };
 504
 505         // Really only [254][11].
 506         static const uint16 g_color8_to_etc_block_config_1_to_254[254][12] =
 507             {
 508                 { 0x021C, 0x0D0D, 0xFFFF }, { 0x0020, 0x0021, 0x0A0B, 0x061F, 0xFFFF }, { 0x0113, 0x0217, 0xFFFF }, { 0x0116, 0x031E,
 509                                                                                                                       0x0B0E, 0x0405, 0xFFFF },
 510                 { 0x0022, 0x0204, 0x050A, 0x0023, 0xFFFF }, { 0x0111, 0x0319, 0x0809, 0x170F, 0xFFFF }, { 0x0303, 0x0215, 0x0607, 0xFFFF }, { 0x0030, 0x0114, 0x0408, 0x0031, 0x0201, 0x051D, 0xFFFF }, { 0x0100, 0x0024, 0x0306,
 511                                                                                                                                                                                                           0x0025, 0x041B, 0x0E0D, 0xFFFF },
 512                 { 0x021A, 0x0121, 0x0B0B, 0x071F, 0xFFFF }, { 0x0213, 0x0317, 0xFFFF }, { 0x0112,
 513                                                                                           0x0505, 0xFFFF },
 514                 { 0x0026, 0x070C, 0x0123, 0x0027, 0xFFFF }, { 0x0211, 0x0909, 0xFFFF }, { 0x0110, 0x0315, 0x0707,
 515                                                                                           0x0419, 0x180F, 0xFFFF },
 516                 { 0x0218, 0x0131, 0x0301, 0x0403, 0x061D, 0xFFFF }, { 0x0032, 0x0202, 0x0033, 0x0125, 0x051B,
 517                                                                       0x0F0D, 0xFFFF },
 518                 { 0x0028, 0x031C, 0x0221, 0x0029, 0xFFFF }, { 0x0120, 0x0313, 0x0C0B, 0x081F, 0xFFFF }, { 0x0605,
 519                                                                                                           0x0417, 0xFFFF },
 520                 { 0x0216, 0x041E, 0x0C0E, 0x0223, 0x0127, 0xFFFF }, { 0x0122, 0x0304, 0x060A, 0x0311, 0x0A09, 0xFFFF }, { 0x0519, 0x190F, 0xFFFF }, { 0x002A, 0x0231, 0x0503, 0x0415, 0x0807, 0x002B, 0x071D, 0xFFFF }, { 0x0130, 0x0214,
 521                                                                                                                                                                                                                           0x0508, 0x0401, 0x0133, 0x0225, 0x061B, 0xFFFF },
 522                 { 0x0200, 0x0124, 0x0406, 0x0321, 0x0129, 0x100D, 0xFFFF }, { 0x031A,
 523                                                                               0x0D0B, 0x091F, 0xFFFF },
 524                 { 0x0413, 0x0705, 0x0517, 0xFFFF }, { 0x0212, 0x0034, 0x0323, 0x0035, 0x0227, 0xFFFF }, { 0x0126, 0x080C, 0x0B09, 0xFFFF }, { 0x0411, 0x0619, 0x1A0F, 0xFFFF }, { 0x0210, 0x0331, 0x0603, 0x0515, 0x0907, 0x012B,
 525                                                                                                                                                                                   0xFFFF },
 526                 { 0x0318, 0x002C, 0x0501, 0x0233, 0x0325, 0x071B, 0x002D, 0x081D, 0xFFFF }, { 0x0132, 0x0302, 0x0229, 0x110D,
 527                                                                                               0xFFFF },
 528                 { 0x0128, 0x041C, 0x0421, 0x0E0B, 0x0A1F, 0xFFFF }, { 0x0220, 0x0513, 0x0617, 0xFFFF }, { 0x0135, 0x0805,
 529                                                                                                           0x0327, 0xFFFF },
 530                 { 0x0316, 0x051E, 0x0D0E, 0x0423, 0xFFFF }, { 0x0222, 0x0404, 0x070A, 0x0511, 0x0719, 0x0C09, 0x1B0F,
 531                                                               0xFFFF },
 532                 { 0x0703, 0x0615, 0x0A07, 0x022B, 0xFFFF }, { 0x012A, 0x0431, 0x0601, 0x0333, 0x012D, 0x091D, 0xFFFF }, { 0x0230, 0x0314, 0x0036, 0x0608, 0x0425, 0x0037, 0x0329, 0x081B, 0x120D, 0xFFFF }, { 0x0300, 0x0224, 0x0506, 0x0521,
 533                                                                                                                                                                                                               0x0F0B, 0x0B1F, 0xFFFF },
 534                 { 0x041A, 0x0613, 0x0717, 0xFFFF }, { 0x0235, 0x0905, 0xFFFF }, { 0x0312, 0x0134, 0x0523,
 535                                                                                   0x0427, 0xFFFF },
 536                 { 0x0226, 0x090C, 0x002E, 0x0611, 0x0D09, 0x002F, 0xFFFF }, { 0x0715, 0x0B07, 0x0819, 0x032B, 0x1C0F,
 537                                                                               0xFFFF },
 538                 { 0x0310, 0x0531, 0x0701, 0x0803, 0x022D, 0x0A1D, 0xFFFF }, { 0x0418, 0x012C, 0x0433, 0x0525, 0x0137, 0x091B,
 539                                                                               0x130D, 0xFFFF },
 540                 { 0x0232, 0x0402, 0x0621, 0x0429, 0xFFFF }, { 0x0228, 0x051C, 0x0713, 0x100B, 0x0C1F, 0xFFFF }, { 0x0320, 0x0335, 0x0A05, 0x0817, 0xFFFF }, { 0x0623, 0x0527, 0xFFFF }, { 0x0416, 0x061E, 0x0E0E, 0x0711, 0x0E09, 0x012F,
 541                                                                                                                                                                                           0xFFFF },
 542                 { 0x0322, 0x0504, 0x080A, 0x0919, 0x1D0F, 0xFFFF }, { 0x0631, 0x0903, 0x0815, 0x0C07, 0x042B, 0x032D, 0x0B1D,
 543                                                                       0xFFFF },
 544                 { 0x022A, 0x0801, 0x0533, 0x0625, 0x0237, 0x0A1B, 0xFFFF }, { 0x0330, 0x0414, 0x0136, 0x0708, 0x0721, 0x0529,
 545                                                                               0x140D, 0xFFFF },
 546                 { 0x0400, 0x0324, 0x0606, 0x0038, 0x0039, 0x110B, 0x0D1F, 0xFFFF }, { 0x051A, 0x0813, 0x0B05, 0x0917,
 547                                                                                       0xFFFF },
 548                 { 0x0723, 0x0435, 0x0627, 0xFFFF }, { 0x0412, 0x0234, 0x0F09, 0x022F, 0xFFFF }, { 0x0326, 0x0A0C, 0x012E,
 549                                                                                                   0x0811, 0x0A19, 0x1E0F, 0xFFFF },
 550                 { 0x0731, 0x0A03, 0x0915, 0x0D07, 0x052B, 0xFFFF }, { 0x0410, 0x0901, 0x0633, 0x0725,
 551                                                                       0x0337, 0x0B1B, 0x042D, 0x0C1D, 0xFFFF },
 552                 { 0x0518, 0x022C, 0x0629, 0x150D, 0xFFFF }, { 0x0332, 0x0502, 0x0821, 0x0139,
 553                                                               0x120B, 0x0E1F, 0xFFFF },
 554                 { 0x0328, 0x061C, 0x0913, 0x0A17, 0xFFFF }, { 0x0420, 0x0535, 0x0C05, 0x0727, 0xFFFF }, { 0x0823, 0x032F, 0xFFFF }, { 0x0516, 0x071E, 0x0F0E, 0x0911, 0x0B19, 0x1009, 0x1F0F, 0xFFFF }, { 0x0422, 0x0604, 0x090A,
 555                                                                                                                                                                                                           0x0B03, 0x0A15, 0x0E07, 0x062B, 0xFFFF },
 556                 { 0x0831, 0x0A01, 0x0733, 0x052D, 0x0D1D, 0xFFFF }, { 0x032A, 0x0825, 0x0437,
 557                                                                       0x0729, 0x0C1B, 0x160D, 0xFFFF },
 558                 { 0x0430, 0x0514, 0x0236, 0x0808, 0x0921, 0x0239, 0x130B, 0x0F1F, 0xFFFF }, { 0x0500,
 559                                                                                               0x0424, 0x0706, 0x0138, 0x0A13, 0x0B17, 0xFFFF },
 560                 { 0x061A, 0x0635, 0x0D05, 0xFFFF }, { 0x0923, 0x0827, 0xFFFF }, { 0x0512, 0x0334, 0x003A, 0x0A11, 0x1109, 0x003B, 0x042F, 0xFFFF }, { 0x0426, 0x0B0C, 0x022E, 0x0B15, 0x0F07, 0x0C19,
 561                                                                                                                                                       0x072B, 0xFFFF },
 562                 { 0x0931, 0x0B01, 0x0C03, 0x062D, 0x0E1D, 0xFFFF }, { 0x0510, 0x0833, 0x0925, 0x0537, 0x0D1B, 0x170D,
 563                                                                       0xFFFF },
 564                 { 0x0618, 0x032C, 0x0A21, 0x0339, 0x0829, 0xFFFF }, { 0x0432, 0x0602, 0x0B13, 0x140B, 0x101F, 0xFFFF }, { 0x0428, 0x071C, 0x0735, 0x0E05, 0x0C17, 0xFFFF }, { 0x0520, 0x0A23, 0x0927, 0xFFFF }, { 0x0B11, 0x1209, 0x013B, 0x052F,
 565                                                                                                                                                                                                                   0xFFFF },
 566                 { 0x0616, 0x081E, 0x0D19, 0xFFFF }, { 0x0522, 0x0704, 0x0A0A, 0x0A31, 0x0D03, 0x0C15, 0x1007, 0x082B, 0x072D,
 567                                                       0x0F1D, 0xFFFF },
 568                 { 0x0C01, 0x0933, 0x0A25, 0x0637, 0x0E1B, 0xFFFF }, { 0x042A, 0x0B21, 0x0929, 0x180D, 0xFFFF }, { 0x0530, 0x0614, 0x0336, 0x0908, 0x0439, 0x150B, 0x111F, 0xFFFF }, { 0x0600, 0x0524, 0x0806, 0x0238, 0x0C13, 0x0F05,
 569                                                                                                                                                                                       0x0D17, 0xFFFF },
 570                 { 0x071A, 0x0B23, 0x0835, 0x0A27, 0xFFFF }, { 0x1309, 0x023B, 0x062F, 0xFFFF }, { 0x0612, 0x0434,
 571                                                                                                   0x013A, 0x0C11, 0x0E19, 0xFFFF },
 572                 { 0x0526, 0x0C0C, 0x032E, 0x0B31, 0x0E03, 0x0D15, 0x1107, 0x092B, 0xFFFF }, { 0x0D01,
 573                                                                                               0x0A33, 0x0B25, 0x0737, 0x0F1B, 0x082D, 0x101D, 0xFFFF },
 574                 { 0x0610, 0x0A29, 0x190D, 0xFFFF }, { 0x0718, 0x042C, 0x0C21,
 575                                                       0x0539, 0x160B, 0x121F, 0xFFFF },
 576                 { 0x0532, 0x0702, 0x0D13, 0x0E17, 0xFFFF }, { 0x0528, 0x081C, 0x0935, 0x1005, 0x0B27,
 577                                                               0xFFFF },
 578                 { 0x0620, 0x0C23, 0x033B, 0x072F, 0xFFFF }, { 0x0D11, 0x0F19, 0x1409, 0xFFFF }, { 0x0716, 0x003C, 0x091E,
 579                                                                                                   0x0F03, 0x0E15, 0x1207, 0x0A2B, 0x003D, 0xFFFF },
 580                 { 0x0622, 0x0804, 0x0B0A, 0x0C31, 0x0E01, 0x0B33, 0x092D, 0x111D,
 581                   0xFFFF },
 582                 { 0x0C25, 0x0837, 0x0B29, 0x101B, 0x1A0D, 0xFFFF }, { 0x052A, 0x0D21, 0x0639, 0x170B, 0x131F, 0xFFFF }, { 0x0630, 0x0714, 0x0436, 0x0A08, 0x0E13, 0x0F17, 0xFFFF }, { 0x0700, 0x0624, 0x0906, 0x0338, 0x0A35, 0x1105, 0xFFFF }, { 0x081A, 0x0D23, 0x0C27, 0xFFFF }, { 0x0E11, 0x1509, 0x043B, 0x082F, 0xFFFF }, { 0x0712, 0x0534, 0x023A, 0x0F15, 0x1307,
 583                                                                                                                                                                                                                                                                                                                                   0x1019, 0x0B2B, 0x013D, 0xFFFF },
 584                 { 0x0626, 0x0D0C, 0x042E, 0x0D31, 0x0F01, 0x1003, 0x0A2D, 0x121D, 0xFFFF }, { 0x0C33,
 585                                                                                               0x0D25, 0x0937, 0x111B, 0x1B0D, 0xFFFF },
 586                 { 0x0710, 0x0E21, 0x0739, 0x0C29, 0xFFFF }, { 0x0818, 0x052C, 0x0F13, 0x180B,
 587                                                               0x141F, 0xFFFF },
 588                 { 0x0632, 0x0802, 0x0B35, 0x1205, 0x1017, 0xFFFF }, { 0x0628, 0x091C, 0x0E23, 0x0D27, 0xFFFF }, { 0x0720, 0x0F11, 0x1609, 0x053B, 0x092F, 0xFFFF }, { 0x1119, 0x023D, 0xFFFF }, { 0x0816, 0x013C, 0x0A1E, 0x0E31, 0x1103,
 589                                                                                                                                                                                                   0x1015, 0x1407, 0x0C2B, 0x0B2D, 0x131D, 0xFFFF },
 590                 { 0x0722, 0x0904, 0x0C0A, 0x1001, 0x0D33, 0x0E25, 0x0A37, 0x121B,
 591                   0xFFFF },
 592                 { 0x0F21, 0x0D29, 0x1C0D, 0xFFFF }, { 0x062A, 0x0839, 0x190B, 0x151F, 0xFFFF }, { 0x0730, 0x0814, 0x0536,
 593                                                                                                   0x0B08, 0x1013, 0x1305, 0x1117, 0xFFFF },
 594                 { 0x0800, 0x0724, 0x0A06, 0x0438, 0x0F23, 0x0C35, 0x0E27, 0xFFFF }, { 0x091A,
 595                                                                                       0x1709, 0x063B, 0x0A2F, 0xFFFF },
 596                 { 0x1011, 0x1219, 0x033D, 0xFFFF }, { 0x0812, 0x0634, 0x033A, 0x0F31, 0x1203, 0x1115,
 597                                                       0x1507, 0x0D2B, 0xFFFF },
 598                 { 0x0726, 0x0E0C, 0x052E, 0x1101, 0x0E33, 0x0F25, 0x0B37, 0x131B, 0x0C2D, 0x141D, 0xFFFF }, { 0x0E29, 0x1D0D, 0xFFFF }, { 0x0810, 0x1021, 0x0939, 0x1A0B, 0x161F, 0xFFFF }, { 0x0918, 0x062C, 0x1113, 0x1217, 0xFFFF }, { 0x0732, 0x0902, 0x0D35, 0x1405, 0x0F27, 0xFFFF }, { 0x0728, 0x0A1C, 0x1023, 0x073B, 0x0B2F, 0xFFFF }, { 0x0820,
 599                                                                                                                                                                                                                                                                                                                                                   0x1111, 0x1319, 0x1809, 0xFFFF },
 600                 { 0x1303, 0x1215, 0x1607, 0x0E2B, 0x043D, 0xFFFF }, { 0x0916, 0x023C, 0x0B1E, 0x1031,
 601                                                                       0x1201, 0x0F33, 0x0D2D, 0x151D, 0xFFFF },
 602                 { 0x0822, 0x0A04, 0x0D0A, 0x1025, 0x0C37, 0x0F29, 0x141B, 0x1E0D, 0xFFFF }, { 0x1121, 0x0A39, 0x1B0B, 0x171F, 0xFFFF }, { 0x072A, 0x1213, 0x1317, 0xFFFF }, { 0x0830, 0x0914, 0x0636, 0x0C08, 0x0E35,
 603                                                                                                                                                                               0x1505, 0xFFFF },
 604                 { 0x0900, 0x0824, 0x0B06, 0x0538, 0x1123, 0x1027, 0xFFFF }, { 0x0A1A, 0x1211, 0x1909, 0x083B, 0x0C2F,
 605                                                                               0xFFFF },
 606                 { 0x1315, 0x1707, 0x1419, 0x0F2B, 0x053D, 0xFFFF }, { 0x0912, 0x0734, 0x043A, 0x1131, 0x1301, 0x1403, 0x0E2D,
 607                                                                       0x161D, 0xFFFF },
 608                 { 0x0826, 0x0F0C, 0x062E, 0x1033, 0x1125, 0x0D37, 0x151B, 0x1F0D, 0xFFFF }, { 0x1221, 0x0B39, 0x1029,
 609                                                                                               0xFFFF },
 610                 { 0x0910, 0x1313, 0x1C0B, 0x181F, 0xFFFF }, { 0x0A18, 0x072C, 0x0F35, 0x1605, 0x1417, 0xFFFF }, { 0x0832,
 611                                                                                                                   0x0A02, 0x1223, 0x1127, 0xFFFF },
 612                 { 0x0828, 0x0B1C, 0x1311, 0x1A09, 0x093B, 0x0D2F, 0xFFFF }, { 0x0920, 0x1519, 0x063D,
 613                                                                               0xFFFF },
 614                 { 0x1231, 0x1503, 0x1415, 0x1807, 0x102B, 0x0F2D, 0x171D, 0xFFFF }, { 0x0A16, 0x033C, 0x0C1E, 0x1401, 0x1133,
 615                                                                                       0x1225, 0x0E37, 0x161B, 0xFFFF },
 616                 { 0x0922, 0x0B04, 0x0E0A, 0x1321, 0x1129, 0xFFFF }, { 0x0C39, 0x1D0B, 0x191F, 0xFFFF }, { 0x082A, 0x1413, 0x1705, 0x1517, 0xFFFF }, { 0x0930, 0x0A14, 0x0736, 0x0D08, 0x1323, 0x1035, 0x1227, 0xFFFF }, { 0x0A00, 0x0924, 0x0C06, 0x0638, 0x1B09, 0x0A3B, 0x0E2F, 0xFFFF }, { 0x0B1A, 0x1411, 0x1619, 0x073D, 0xFFFF }, { 0x1331,
 617                                                                                                                                                                                                                                                                                                                                           0x1603, 0x1515, 0x1907, 0x112B, 0xFFFF },
 618                 { 0x0A12, 0x0834, 0x053A, 0x1501, 0x1233, 0x1325, 0x0F37, 0x171B, 0x102D,
 619                   0x181D, 0xFFFF },
 620                 { 0x0926, 0x072E, 0x1229, 0xFFFF }, { 0x1421, 0x0D39, 0x1E0B, 0x1A1F, 0xFFFF }, { 0x0A10, 0x1513,
 621                                                                                                   0x1617, 0xFFFF },
 622                 { 0x0B18, 0x082C, 0x1135, 0x1805, 0x1327, 0xFFFF }, { 0x0932, 0x0B02, 0x1423, 0x0B3B, 0x0F2F, 0xFFFF }, { 0x0928, 0x0C1C, 0x1511, 0x1719, 0x1C09, 0xFFFF }, { 0x0A20, 0x1703, 0x1615, 0x1A07, 0x122B, 0x083D, 0xFFFF }, { 0x1431, 0x1601, 0x1333, 0x112D, 0x191D, 0xFFFF }, { 0x0B16, 0x043C, 0x0D1E, 0x1425, 0x1037, 0x1329, 0x181B, 0xFFFF }, { 0x0A22, 0x0C04, 0x0F0A, 0x1521, 0x0E39, 0x1F0B, 0x1B1F, 0xFFFF }, { 0x1613, 0x1717, 0xFFFF }, { 0x092A, 0x1235, 0x1905,
 623                                                                                                                                                                                                                                                                                                                                                                                                                                                                   0xFFFF },
 624                 { 0x0A30, 0x0B14, 0x0836, 0x0E08, 0x1523, 0x1427, 0xFFFF }, { 0x0B00, 0x0A24, 0x0D06, 0x0738, 0x1611, 0x1D09,
 625                                                                               0x0C3B, 0x102F, 0xFFFF },
 626                 { 0x0C1A, 0x1715, 0x1B07, 0x1819, 0x132B, 0x093D, 0xFFFF }, { 0x1531, 0x1701, 0x1803, 0x122D,
 627                                                                               0x1A1D, 0xFFFF },
 628                 { 0x0B12, 0x0934, 0x063A, 0x1433, 0x1525, 0x1137, 0x191B, 0xFFFF }, { 0x0A26, 0x003E, 0x082E, 0x1621,
 629                                                                                       0x0F39, 0x1429, 0x003F, 0xFFFF },
 630                 { 0x1713, 0x1C1F, 0xFFFF }, { 0x0B10, 0x1335, 0x1A05, 0x1817, 0xFFFF }, { 0x0C18,
 631                                                                                           0x092C, 0x1623, 0x1527, 0xFFFF },
 632                 { 0x0A32, 0x0C02, 0x1711, 0x1E09, 0x0D3B, 0x112F, 0xFFFF }, { 0x0A28, 0x0D1C, 0x1919,
 633                                                                               0x0A3D, 0xFFFF },
 634                 { 0x0B20, 0x1631, 0x1903, 0x1815, 0x1C07, 0x142B, 0x132D, 0x1B1D, 0xFFFF }, { 0x1801, 0x1533, 0x1625,
 635                                                                                               0x1237, 0x1A1B, 0xFFFF },
 636                 { 0x0C16, 0x053C, 0x0E1E, 0x1721, 0x1529, 0x013F, 0xFFFF }, { 0x0B22, 0x0D04, 0x1039, 0x1D1F,
 637                                                                               0xFFFF },
 638                 { 0x1813, 0x1B05, 0x1917, 0xFFFF }, { 0x0A2A, 0x1723, 0x1435, 0x1627, 0xFFFF }, { 0x0B30, 0x0C14, 0x0936,
 639                                                                                                   0x0F08, 0x1F09, 0x0E3B, 0x122F, 0xFFFF },
 640                 { 0x0C00, 0x0B24, 0x0E06, 0x0838, 0x1811, 0x1A19, 0x0B3D, 0xFFFF }, { 0x0D1A,
 641                                                                                       0x1731, 0x1A03, 0x1915, 0x1D07, 0x152B, 0xFFFF },
 642                 { 0x1901, 0x1633, 0x1725, 0x1337, 0x1B1B, 0x142D, 0x1C1D, 0xFFFF }, { 0x0C12, 0x0A34, 0x073A, 0x1629, 0x023F, 0xFFFF }, { 0x0B26, 0x013E, 0x092E, 0x1821, 0x1139, 0x1E1F, 0xFFFF }, { 0x1913,
 643                                                                                                                                                                                                       0x1A17, 0xFFFF },
 644                 { 0x0C10, 0x1535, 0x1C05, 0x1727, 0xFFFF }, { 0x0D18, 0x0A2C, 0x1823, 0x0F3B, 0x132F, 0xFFFF }, { 0x0B32, 0x0D02, 0x1911, 0x1B19, 0xFFFF }, { 0x0B28, 0x0E1C, 0x1B03, 0x1A15, 0x1E07, 0x162B, 0x0C3D, 0xFFFF }, { 0x0C20,
 645                                                                                                                                                                                                                                   0x1831, 0x1A01, 0x1733, 0x152D, 0x1D1D, 0xFFFF },
 646                 { 0x1825, 0x1437, 0x1729, 0x1C1B, 0x033F, 0xFFFF }, { 0x0D16, 0x063C,
 647                                                                       0x0F1E, 0x1921, 0x1239, 0x1F1F, 0xFFFF },
 648                 { 0x0C22, 0x0E04, 0x1A13, 0x1B17, 0xFFFF }, { 0x1635, 0x1D05, 0xFFFF }, { 0x0B2A, 0x1923, 0x1827, 0xFFFF }, { 0x0C30, 0x0D14, 0x0A36, 0x1A11, 0x103B, 0x142F, 0xFFFF }, { 0x0D00, 0x0C24, 0x0F06,
 649                                                                                                                                                                                           0x0938, 0x1B15, 0x1F07, 0x1C19, 0x172B, 0x0D3D, 0xFFFF },
 650                 { 0x0E1A, 0x1931, 0x1B01, 0x1C03, 0x162D, 0x1E1D, 0xFFFF }, { 0x1833, 0x1925, 0x1537, 0x1D1B, 0xFFFF }, { 0x0D12, 0x0B34, 0x083A, 0x1A21, 0x1339, 0x1829, 0x043F, 0xFFFF }, { 0x0C26,
 651                                                                                                                                                                                               0x023E, 0x0A2E, 0x1B13, 0xFFFF },
 652                 { 0x1735, 0x1E05, 0x1C17, 0xFFFF }, { 0x0D10, 0x1A23, 0x1927, 0xFFFF }, { 0x0E18,
 653                                                                                           0x0B2C, 0x1B11, 0x113B, 0x152F, 0xFFFF },
 654                 { 0x0C32, 0x0E02, 0x1D19, 0x0E3D, 0xFFFF }, { 0x0C28, 0x0F1C, 0x1A31, 0x1D03,
 655                                                               0x1C15, 0x182B, 0x172D, 0x1F1D, 0xFFFF },
 656                 { 0x0D20, 0x1C01, 0x1933, 0x1A25, 0x1637, 0x1E1B, 0xFFFF }, { 0x1B21, 0x1929,
 657                                                                               0x053F, 0xFFFF },
 658                 { 0x0E16, 0x073C, 0x1439, 0xFFFF }, { 0x0D22, 0x0F04, 0x1C13, 0x1F05, 0x1D17, 0xFFFF }, { 0x1B23,
 659                                                                                                           0x1835, 0x1A27, 0xFFFF },
 660                 { 0x0C2A, 0x123B, 0x162F, 0xFFFF }, { 0x0D30, 0x0E14, 0x0B36, 0x1C11, 0x1E19, 0x0F3D, 0xFFFF }, { 0x0E00, 0x0D24, 0x0A38, 0x1B31, 0x1E03, 0x1D15, 0x192B, 0xFFFF }, { 0x0F1A, 0x1D01, 0x1A33, 0x1B25, 0x1737, 0x1F1B,
 661                                                                                                                                                                                       0x182D, 0xFFFF },
 662                 { 0x1A29, 0x063F, 0xFFFF }, { 0x0E12, 0x0C34, 0x093A, 0x1C21, 0x1539, 0xFFFF }, { 0x0D26, 0x033E,
 663                                                                                                   0x0B2E, 0x1D13, 0x1E17, 0xFFFF },
 664                 { 0x1935, 0x1B27, 0xFFFF }, { 0x0E10, 0x1C23, 0x133B, 0x172F, 0xFFFF }, { 0x0F18,
 665                                                                                           0x0C2C, 0x1D11, 0x1F19, 0xFFFF },
 666                 { 0x0D32, 0x0F02, 0x1F03, 0x1E15, 0x1A2B, 0x103D, 0xFFFF }, { 0x0D28, 0x1C31, 0x1E01,
 667                                                                               0x1B33, 0x192D, 0xFFFF },
 668                 { 0x0E20, 0x1C25, 0x1837, 0x1B29, 0x073F, 0xFFFF }, { 0x1D21, 0x1639, 0xFFFF }, { 0x0F16,
 669                                                                                                   0x083C, 0x1E13, 0x1F17, 0xFFFF },
 670                 { 0x0E22, 0x1A35, 0xFFFF }, { 0x1D23, 0x1C27, 0xFFFF }, { 0x0D2A, 0x1E11, 0x143B,
 671                                                                           0x182F, 0xFFFF },
 672                 { 0x0E30, 0x0F14, 0x0C36, 0x1F15, 0x1B2B, 0x113D, 0xFFFF }, { 0x0F00, 0x0E24, 0x0B38, 0x1D31, 0x1F01,
 673                                                                               0x1A2D, 0xFFFF },
 674                 { 0x1C33, 0x1D25, 0x1937, 0xFFFF }, { 0x1E21, 0x1739, 0x1C29, 0x083F, 0xFFFF }, { 0x0F12, 0x0D34,
 675                                                                                                   0x0A3A, 0x1F13, 0xFFFF },
 676                 { 0x0E26, 0x043E, 0x0C2E, 0x1B35, 0xFFFF }, { 0x1E23, 0x1D27, 0xFFFF }, { 0x0F10, 0x1F11,
 677                                                                                           0x153B, 0x192F, 0xFFFF },
 678                 { 0x0D2C, 0x123D, 0xFFFF },
 679             };
 680
 681         struct etc1_block
 682         {
 683             // big endian uint64_t:
 684             // bit ofs:  56  48  40  32  24  16   8   0
 685             // byte ofs: b0, b1, b2, b3, b4, b5, b6, b7
 686             union
 687             {
 688                 uint64_t m_uint64;
 689                 uint8 m_bytes[8];
 690             };
 691
 692             uint8 m_low_color[2];
 693             uint8 m_high_color[2];
 694
 695             enum
 696             {
 697                 cNumSelectorBytes = 4
 698             };
 699             uint8 m_selectors[cNumSelectorBytes];
 700
 701             inline void clear()
 702             {
 703                 zero_this(this);
 704             }
 705
 706             inline uint get_byte_bits(uint ofs, uint num) const
 707             {
 708                 RG_ETC1_ASSERT((ofs + num) <= 64U);
 709                 RG_ETC1_ASSERT(num && (num <= 8U));
 710                 RG_ETC1_ASSERT((ofs >> 3) == ((ofs + num - 1) >> 3));
 711                 const uint byte_ofs = 7 - (ofs >> 3);
 712                 const uint byte_bit_ofs = ofs & 7;
 713                 return (m_bytes[byte_ofs] >> byte_bit_ofs) & ((1 << num) - 1);
 714             }
 715
 716             inline void set_byte_bits(uint ofs, uint num, uint bits)
 717             {
 718                 RG_ETC1_ASSERT((ofs + num) <= 64U);
 719                 RG_ETC1_ASSERT(num && (num < 32U));
 720                 RG_ETC1_ASSERT((ofs >> 3) == ((ofs + num - 1) >> 3));
 721                 RG_ETC1_ASSERT(bits < (1U << num));
 722                 const uint byte_ofs = 7 - (ofs >> 3);
 723                 const uint byte_bit_ofs = ofs & 7;
 724                 const uint mask = (1 << num) - 1;
 725                 m_bytes[byte_ofs] &= ~(mask << byte_bit_ofs);
 726                 m_bytes[byte_ofs] |= (bits << byte_bit_ofs);
 727             }
 728
 729             // false = left/right subblocks
 730             // true = upper/lower subblocks
 731             inline bool get_flip_bit() const
 732             {
 733                 return (m_bytes[3] & 1) != 0;
 734             }
 735
 736             inline void set_flip_bit(bool flip)
 737             {
 738                 m_bytes[3] &= ~1;
 739                 m_bytes[3] |= static_cast<uint8>(flip);
 740             }
 741
 742             inline bool get_diff_bit() const
 743             {
 744                 return (m_bytes[3] & 2) != 0;
 745             }
 746
 747             inline void set_diff_bit(bool diff)
 748             {
 749                 m_bytes[3] &= ~2;
 750                 m_bytes[3] |= (static_cast<uint>(diff) << 1);
 751             }
 752
 753             // Returns intensity modifier table (0-7) used by subblock subblock_id.
 754             // subblock_id=0 left/top (CW 1), 1=right/bottom (CW 2)
 755             inline uint get_inten_table(uint subblock_id) const
 756             {
 757                 RG_ETC1_ASSERT(subblock_id < 2);
 758                 const uint ofs = subblock_id ? 2 : 5;
 759                 return (m_bytes[3] >> ofs) & 7;
 760             }
 761
 762             // Sets intensity modifier table (0-7) used by subblock subblock_id (0 or 1)
 763             inline void set_inten_table(uint subblock_id, uint t)
 764             {
 765                 RG_ETC1_ASSERT(subblock_id < 2);
 766                 RG_ETC1_ASSERT(t < 8);
 767                 const uint ofs = subblock_id ? 2 : 5;
 768                 m_bytes[3] &= ~(7 << ofs);
 769                 m_bytes[3] |= (t << ofs);
 770             }
 771
 772             // Returned selector value ranges from 0-3 and is a direct index into g_etc1_inten_tables.
 773             inline uint get_selector(uint x, uint y) const
 774             {
 775                 RG_ETC1_ASSERT((x | y) < 4);
 776
 777                 const uint bit_index = x * 4 + y;
 778                 const uint byte_bit_ofs = bit_index & 7;
 779                 const uint8 *p = &m_bytes[7 - (bit_index >> 3)];
 780                 const uint lsb = (p[0] >> byte_bit_ofs) & 1;
 781                 const uint msb = (p[-2] >> byte_bit_ofs) & 1;
 782                 const uint val = lsb | (msb << 1);
 783
 784                 return g_etc1_to_selector_index[val];
 785             }
 786
 787             // Selector "val" ranges from 0-3 and is a direct index into g_etc1_inten_tables.
 788             inline void set_selector(uint x, uint y, uint val)
 789             {
 790                 RG_ETC1_ASSERT((x | y | val) < 4);
 791                 const uint bit_index = x * 4 + y;
 792
 793                 uint8 *p = &m_bytes[7 - (bit_index >> 3)];
 794
 795                 const uint byte_bit_ofs = bit_index & 7;
 796                 const uint mask = 1 << byte_bit_ofs;
 797
 798                 const uint etc1_val = g_selector_index_to_etc1[val];
 799
 800                 const uint lsb = etc1_val & 1;
 801                 const uint msb = etc1_val >> 1;
 802
 803                 p[0] &= ~mask;
 804                 p[0] |= (lsb << byte_bit_ofs);
 805
 806                 p[-2] &= ~mask;
 807                 p[-2] |= (msb << byte_bit_ofs);
 808             }
 809
 810             inline void set_base4_color(uint idx, uint16 c)
 811             {
 812                 if (idx)
 813                 {
 814                     set_byte_bits(cETC1AbsColor4R2BitOffset, 4, (c >> 8) & 15);
 815                     set_byte_bits(cETC1AbsColor4G2BitOffset, 4, (c >> 4) & 15);
 816                     set_byte_bits(cETC1AbsColor4B2BitOffset, 4, c & 15);
 817                 }
 818                 else
 819                 {
 820                     set_byte_bits(cETC1AbsColor4R1BitOffset, 4, (c >> 8) & 15);
 821                     set_byte_bits(cETC1AbsColor4G1BitOffset, 4, (c >> 4) & 15);
 822                     set_byte_bits(cETC1AbsColor4B1BitOffset, 4, c & 15);
 823                 }
 824             }
 825
 826             inline uint16 get_base4_color(uint idx) const
 827             {
 828                 uint r, g, b;
 829                 if (idx)
 830                 {
 831                     r = get_byte_bits(cETC1AbsColor4R2BitOffset, 4);
 832                     g = get_byte_bits(cETC1AbsColor4G2BitOffset, 4);
 833                     b = get_byte_bits(cETC1AbsColor4B2BitOffset, 4);
 834                 }
 835                 else
 836                 {
 837                     r = get_byte_bits(cETC1AbsColor4R1BitOffset, 4);
 838                     g = get_byte_bits(cETC1AbsColor4G1BitOffset, 4);
 839                     b = get_byte_bits(cETC1AbsColor4B1BitOffset, 4);
 840                 }
 841                 return static_cast<uint16>(b | (g << 4U) | (r << 8U));
 842             }
 843
 844             inline void set_base5_color(uint16 c)
 845             {
 846                 set_byte_bits(cETC1BaseColor5RBitOffset, 5, (c >> 10) & 31);
 847                 set_byte_bits(cETC1BaseColor5GBitOffset, 5, (c >> 5) & 31);
 848                 set_byte_bits(cETC1BaseColor5BBitOffset, 5, c & 31);
 849             }
 850
 851             inline uint16 get_base5_color() const
 852             {
 853                 const uint r = get_byte_bits(cETC1BaseColor5RBitOffset, 5);
 854                 const uint g = get_byte_bits(cETC1BaseColor5GBitOffset, 5);
 855                 const uint b = get_byte_bits(cETC1BaseColor5BBitOffset, 5);
 856                 return static_cast<uint16>(b | (g << 5U) | (r << 10U));
 857             }
 858
 859             void set_delta3_color(uint16 c)
 860             {
 861                 set_byte_bits(cETC1DeltaColor3RBitOffset, 3, (c >> 6) & 7);
 862                 set_byte_bits(cETC1DeltaColor3GBitOffset, 3, (c >> 3) & 7);
 863                 set_byte_bits(cETC1DeltaColor3BBitOffset, 3, c & 7);
 864             }
 865
 866             inline uint16 get_delta3_color() const
 867             {
 868                 const uint r = get_byte_bits(cETC1DeltaColor3RBitOffset, 3);
 869                 const uint g = get_byte_bits(cETC1DeltaColor3GBitOffset, 3);
 870                 const uint b = get_byte_bits(cETC1DeltaColor3BBitOffset, 3);
 871                 return static_cast<uint16>(b | (g << 3U) | (r << 6U));
 872             }
 873
 874             // Base color 5
 875             static uint16 pack_color5(const color_quad_u8 &color, bool scaled, uint bias = 127U);
 876             static uint16 pack_color5(uint r, uint g, uint b, bool scaled, uint bias = 127U);
 877
 878             static color_quad_u8 unpack_color5(uint16 packed_color5, bool scaled, uint alpha = 255U);
 879             static void unpack_color5(uint &r, uint &g, uint &b, uint16 packed_color, bool scaled);
 880
 881             static bool unpack_color5(color_quad_u8 &result, uint16 packed_color5, uint16 packed_delta3, bool scaled, uint alpha = 255U);
 882             static bool unpack_color5(uint &r, uint &g, uint &b, uint16 packed_color5, uint16 packed_delta3, bool scaled, uint alpha = 255U);
 883
 884             // Delta color 3
 885             // Inputs range from -4 to 3 (cETC1ColorDeltaMin to cETC1ColorDeltaMax)
 886             static uint16 pack_delta3(int r, int g, int b);
 887
 888             // Results range from -4 to 3 (cETC1ColorDeltaMin to cETC1ColorDeltaMax)
 889             static void unpack_delta3(int &r, int &g, int &b, uint16 packed_delta3);
 890
 891             // Abs color 4
 892             static uint16 pack_color4(const color_quad_u8 &color, bool scaled, uint bias = 127U);
 893             static uint16 pack_color4(uint r, uint g, uint b, bool scaled, uint bias = 127U);
 894
 895             static color_quad_u8 unpack_color4(uint16 packed_color4, bool scaled, uint alpha = 255U);
 896             static void unpack_color4(uint &r, uint &g, uint &b, uint16 packed_color4, bool scaled);
 897
 898             // subblock colors
 899             static void get_diff_subblock_colors(color_quad_u8 *pDst, uint16 packed_color5, uint table_idx);
 900             static bool get_diff_subblock_colors(color_quad_u8 *pDst, uint16 packed_color5, uint16 packed_delta3, uint table_idx);
 901             static void get_abs_subblock_colors(color_quad_u8 *pDst, uint16 packed_color4, uint table_idx);
 902
 903             static inline void unscaled_to_scaled_color(color_quad_u8 &dst, const color_quad_u8 &src, bool color4)
 904             {
 905                 if (color4)
 906                 {
 907                     dst.r = src.r | (src.r << 4);
 908                     dst.g = src.g | (src.g << 4);
 909                     dst.b = src.b | (src.b << 4);
 910                 }
 911                 else
 912                 {
 913                     dst.r = (src.r >> 2) | (src.r << 3);
 914                     dst.g = (src.g >> 2) | (src.g << 3);
 915                     dst.b = (src.b >> 2) | (src.b << 3);
 916                 }
 917                 dst.a = src.a;
 918             }
 919         };
 920
 921         // Returns pointer to sorted array.
 922         template <typename T, typename Q>
 923         T *indirect_radix_sort(uint num_indices, T *pIndices0, T *pIndices1, const Q *pKeys, uint key_ofs, uint key_size, bool init_indices)
 924         {
 925             //RG_ETC1_ASSERT((key_ofs >= 0) && (key_ofs < sizeof(T)));
 926             RG_ETC1_ASSERT(key_ofs < sizeof(T));
 927             RG_ETC1_ASSERT((key_size >= 1) && (key_size <= 4));
 928
 929             if (init_indices)
 930             {
 931                 T *p = pIndices0;
 932                 T *q = pIndices0 + (num_indices >> 1) * 2;
 933                 uint i;
 934                 for (i = 0; p != q; p += 2, i += 2)
 935                 {
 936                     p[0] = static_cast<T>(i);
 937                     p[1] = static_cast<T>(i + 1);
 938                 }
 939
 940                 if (num_indices & 1)
 941                     *p = static_cast<T>(i);
 942             }
 943
 944             uint hist[256 * 4];
 945
 946             memset(hist, 0, sizeof(hist[0]) * 256 * key_size);
 947
 948 #define RG_ETC1_GET_KEY(p) (*(const uint *)((const uint8 *)(pKeys + *(p)) + key_ofs))
 949 #define RG_ETC1_GET_KEY_FROM_INDEX(i) (*(const uint *)((const uint8 *)(pKeys + (i)) + key_ofs))
 950
 951             if (key_size == 4)
 952             {
 953                 T *p = pIndices0;
 954                 T *q = pIndices0 + num_indices;
 955                 for (; p != q; p++)
 956                 {
 957                     const uint key = RG_ETC1_GET_KEY(p);
 958
 959                     hist[key & 0xFF]++;
 960                     hist[256 + ((key >> 8) & 0xFF)]++;
 961                     hist[512 + ((key >> 16) & 0xFF)]++;
 962                     hist[768 + ((key >> 24) & 0xFF)]++;
 963                 }
 964             }
 965             else if (key_size == 3)
 966             {
 967                 T *p = pIndices0;
 968                 T *q = pIndices0 + num_indices;
 969                 for (; p != q; p++)
 970                 {
 971                     const uint key = RG_ETC1_GET_KEY(p);
 972
 973                     hist[key & 0xFF]++;
 974                     hist[256 + ((key >> 8) & 0xFF)]++;
 975                     hist[512 + ((key >> 16) & 0xFF)]++;
 976                 }
 977             }
 978             else if (key_size == 2)
 979             {
 980                 T *p = pIndices0;
 981                 T *q = pIndices0 + (num_indices >> 1) * 2;
 982
 983                 for (; p != q; p += 2)
 984                 {
 985                     const uint key0 = RG_ETC1_GET_KEY(p);
 986                     const uint key1 = RG_ETC1_GET_KEY(p + 1);
 987
 988                     hist[key0 & 0xFF]++;
 989                     hist[256 + ((key0 >> 8) & 0xFF)]++;
 990
 991                     hist[key1 & 0xFF]++;
 992                     hist[256 + ((key1 >> 8) & 0xFF)]++;
 993                 }
 994
 995                 if (num_indices & 1)
 996                 {
 997                     const uint key = RG_ETC1_GET_KEY(p);
 998
 999                     hist[key & 0xFF]++;
1000                     hist[256 + ((key >> 8) & 0xFF)]++;
1001                 }
1002             }
1003             else
1004             {
1005                 RG_ETC1_ASSERT(key_size == 1);
1006                 if (key_size != 1)
1007                     return NULL;
1008
1009                 T *p = pIndices0;
1010                 T *q = pIndices0 + (num_indices >> 1) * 2;
1011
1012                 for (; p != q; p += 2)
1013                 {
1014                     const uint key0 = RG_ETC1_GET_KEY(p);
1015                     const uint key1 = RG_ETC1_GET_KEY(p + 1);
1016
1017                     hist[key0 & 0xFF]++;
1018                     hist[key1 & 0xFF]++;
1019                 }
1020
1021                 if (num_indices & 1)
1022                 {
1023                     const uint key = RG_ETC1_GET_KEY(p);
1024
1025                     hist[key & 0xFF]++;
1026                 }
1027             }
1028
1029             T *pCur = pIndices0;
1030             T *pNew = pIndices1;
1031
1032             for (uint pass = 0; pass < key_size; pass++)
1033             {
1034                 const uint *pHist = &hist[pass << 8];
1035
1036                 uint offsets[256];
1037
1038                 uint cur_ofs = 0;
1039                 for (uint i = 0; i < 256; i += 2)
1040                 {
1041                     offsets[i] = cur_ofs;
1042                     cur_ofs += pHist[i];
1043
1044                     offsets[i + 1] = cur_ofs;
1045                     cur_ofs += pHist[i + 1];
1046                 }
1047
1048                 const uint pass_shift = pass << 3;
1049
1050                 T *p = pCur;
1051                 T *q = pCur + (num_indices >> 1) * 2;
1052
1053                 for (; p != q; p += 2)
1054                 {
1055                     uint index0 = p[0];
1056                     uint index1 = p[1];
1057
1058                     uint c0 = (RG_ETC1_GET_KEY_FROM_INDEX(index0) >> pass_shift) & 0xFF;
1059                     uint c1 = (RG_ETC1_GET_KEY_FROM_INDEX(index1) >> pass_shift) & 0xFF;
1060
1061                     if (c0 == c1)
1062                     {
1063                         uint dst_offset0 = offsets[c0];
1064
1065                         offsets[c0] = dst_offset0 + 2;
1066
1067                         pNew[dst_offset0] = static_cast<T>(index0);
1068                         pNew[dst_offset0 + 1] = static_cast<T>(index1);
1069                     }
1070                     else
1071                     {
1072                         uint dst_offset0 = offsets[c0]++;
1073                         uint dst_offset1 = offsets[c1]++;
1074
1075                         pNew[dst_offset0] = static_cast<T>(index0);
1076                         pNew[dst_offset1] = static_cast<T>(index1);
1077                     }
1078                 }
1079
1080                 if (num_indices & 1)
1081                 {
1082                     uint index = *p;
1083                     uint c = (RG_ETC1_GET_KEY_FROM_INDEX(index) >> pass_shift) & 0xFF;
1084
1085                     uint dst_offset = offsets[c];
1086                     offsets[c] = dst_offset + 1;
1087
1088                     pNew[dst_offset] = static_cast<T>(index);
1089                 }
1090
1091                 T *t = pCur;
1092                 pCur = pNew;
1093                 pNew = t;
1094             }
1095
1096             return pCur;
1097         }
1098
1099 #undef RG_ETC1_GET_KEY
1100 #undef RG_ETC1_GET_KEY_FROM_INDEX
1101
1102         uint16 etc1_block::pack_color5(const color_quad_u8 &color, bool scaled, uint bias)
1103         {
1104             return pack_color5(color.r, color.g, color.b, scaled, bias);
1105         }
1106
1107         uint16 etc1_block::pack_color5(uint r, uint g, uint b, bool scaled, uint bias)
1108         {
1109             if (scaled)
1110             {
1111                 r = (r * 31U + bias) / 255U;
1112                 g = (g * 31U + bias) / 255U;
1113                 b = (b * 31U + bias) / 255U;
1114             }
1115
1116             r = rg_etc1::minimum(r, 31U);
1117             g = rg_etc1::minimum(g, 31U);
1118             b = rg_etc1::minimum(b, 31U);
1119
1120             return static_cast<uint16>(b | (g << 5U) | (r << 10U));
1121         }
1122
1123         color_quad_u8 etc1_block::unpack_color5(uint16 packed_color5, bool scaled, uint alpha)
1124         {
1125             uint b = packed_color5 & 31U;
1126             uint g = (packed_color5 >> 5U) & 31U;
1127             uint r = (packed_color5 >> 10U) & 31U;
1128
1129             if (scaled)
1130             {
1131                 b = (b << 3U) | (b >> 2U);
1132                 g = (g << 3U) | (g >> 2U);
1133                 r = (r << 3U) | (r >> 2U);
1134             }
1135
1136             return color_quad_u8(cNoClamp, r, g, b, rg_etc1::minimum(alpha, 255U));
1137         }
1138
1139         void etc1_block::unpack_color5(uint &r, uint &g, uint &b, uint16 packed_color5, bool scaled)
1140         {
1141             color_quad_u8 c(unpack_color5(packed_color5, scaled, 0));
1142             r = c.r;
1143             g = c.g;
1144             b = c.b;
1145         }
1146
1147         bool etc1_block::unpack_color5(color_quad_u8 &result, uint16 packed_color5, uint16 packed_delta3, bool scaled, uint alpha)
1148         {
1149             int dc_r, dc_g, dc_b;
1150             unpack_delta3(dc_r, dc_g, dc_b, packed_delta3);
1151
1152             int b = (packed_color5 & 31U) + dc_b;
1153             int g = ((packed_color5 >> 5U) & 31U) + dc_g;
1154             int r = ((packed_color5 >> 10U) & 31U) + dc_r;
1155
1156             bool success = true;
1157             if (static_cast<uint>(r | g | b) > 31U)
1158             {
1159                 success = false;
1160                 r = rg_etc1::clamp<int>(r, 0, 31);
1161                 g = rg_etc1::clamp<int>(g, 0, 31);
1162                 b = rg_etc1::clamp<int>(b, 0, 31);
1163             }
1164
1165             if (scaled)
1166             {
1167                 b = (b << 3U) | (b >> 2U);
1168                 g = (g << 3U) | (g >> 2U);
1169                 r = (r << 3U) | (r >> 2U);
1170             }
1171
1172             result.set_noclamp_rgba(r, g, b, rg_etc1::minimum(alpha, 255U));
1173             return success;
1174         }
1175
1176         bool etc1_block::unpack_color5(uint &r, uint &g, uint &b, uint16 packed_color5, uint16 packed_delta3, bool scaled, uint alpha)
1177         {
1178             color_quad_u8 result;
1179             const bool success = unpack_color5(result, packed_color5, packed_delta3, scaled, alpha);
1180             r = result.r;
1181             g = result.g;
1182             b = result.b;
1183             return success;
1184         }
1185
1186         uint16 etc1_block::pack_delta3(int r, int g, int b)
1187         {
1188             RG_ETC1_ASSERT((r >= cETC1ColorDeltaMin) && (r <= cETC1ColorDeltaMax));
1189             RG_ETC1_ASSERT((g >= cETC1ColorDeltaMin) && (g <= cETC1ColorDeltaMax));
1190             RG_ETC1_ASSERT((b >= cETC1ColorDeltaMin) && (b <= cETC1ColorDeltaMax));
1191             if (r < 0)
1192                 r += 8;
1193             if (g < 0)
1194                 g += 8;
1195             if (b < 0)
1196                 b += 8;
1197             return static_cast<uint16>(b | (g << 3) | (r << 6));
1198         }
1199
1200         void etc1_block::unpack_delta3(int &r, int &g, int &b, uint16 packed_delta3)
1201         {
1202             r = (packed_delta3 >> 6) & 7;
1203             g = (packed_delta3 >> 3) & 7;
1204             b = packed_delta3 & 7;
1205             if (r >= 4)
1206                 r -= 8;
1207             if (g >= 4)
1208                 g -= 8;
1209             if (b >= 4)
1210                 b -= 8;
1211         }
1212
1213         uint16 etc1_block::pack_color4(const color_quad_u8 &color, bool scaled, uint bias)
1214         {
1215             return pack_color4(color.r, color.g, color.b, scaled, bias);
1216         }
1217
1218         uint16 etc1_block::pack_color4(uint r, uint g, uint b, bool scaled, uint bias)
1219         {
1220             if (scaled)
1221             {
1222                 r = (r * 15U + bias) / 255U;
1223                 g = (g * 15U + bias) / 255U;
1224                 b = (b * 15U + bias) / 255U;
1225             }
1226
1227             r = rg_etc1::minimum(r, 15U);
1228             g = rg_etc1::minimum(g, 15U);
1229             b = rg_etc1::minimum(b, 15U);
1230
1231             return static_cast<uint16>(b | (g << 4U) | (r << 8U));
1232         }
1233
1234         color_quad_u8 etc1_block::unpack_color4(uint16 packed_color4, bool scaled, uint alpha)
1235         {
1236             uint b = packed_color4 & 15U;
1237             uint g = (packed_color4 >> 4U) & 15U;
1238             uint r = (packed_color4 >> 8U) & 15U;
1239
1240             if (scaled)
1241             {
1242                 b = (b << 4U) | b;
1243                 g = (g << 4U) | g;
1244                 r = (r << 4U) | r;
1245             }
1246
1247             return color_quad_u8(cNoClamp, r, g, b, rg_etc1::minimum(alpha, 255U));
1248         }
1249
1250         void etc1_block::unpack_color4(uint &r, uint &g, uint &b, uint16 packed_color4, bool scaled)
1251         {
1252             color_quad_u8 c(unpack_color4(packed_color4, scaled, 0));
1253             r = c.r;
1254             g = c.g;
1255             b = c.b;
1256         }
1257
1258         void etc1_block::get_diff_subblock_colors(color_quad_u8 *pDst, uint16 packed_color5, uint table_idx)
1259         {
1260             RG_ETC1_ASSERT(table_idx < cETC1IntenModifierValues);
1261             const int *pInten_modifer_table = &g_etc1_inten_tables[table_idx][0];
1262
1263             uint r, g, b;
1264             unpack_color5(r, g, b, packed_color5, true);
1265
1266             const int ir = static_cast<int>(r), ig = static_cast<int>(g), ib = static_cast<int>(b);
1267
1268             const int y0 = pInten_modifer_table[0];
1269             pDst[0].set(ir + y0, ig + y0, ib + y0);
1270
1271             const int y1 = pInten_modifer_table[1];
1272             pDst[1].set(ir + y1, ig + y1, ib + y1);
1273
1274             const int y2 = pInten_modifer_table[2];
1275             pDst[2].set(ir + y2, ig + y2, ib + y2);
1276
1277             const int y3 = pInten_modifer_table[3];
1278             pDst[3].set(ir + y3, ig + y3, ib + y3);
1279         }
1280
1281         bool etc1_block::get_diff_subblock_colors(color_quad_u8 *pDst, uint16 packed_color5, uint16 packed_delta3, uint table_idx)
1282         {
1283             RG_ETC1_ASSERT(table_idx < cETC1IntenModifierValues);
1284             const int *pInten_modifer_table = &g_etc1_inten_tables[table_idx][0];
1285
1286             uint r, g, b;
1287             bool success = unpack_color5(r, g, b, packed_color5, packed_delta3, true);
1288
1289             const int ir = static_cast<int>(r), ig = static_cast<int>(g), ib = static_cast<int>(b);
1290
1291             const int y0 = pInten_modifer_table[0];
1292             pDst[0].set(ir + y0, ig + y0, ib + y0);
1293
1294             const int y1 = pInten_modifer_table[1];
1295             pDst[1].set(ir + y1, ig + y1, ib + y1);
1296
1297             const int y2 = pInten_modifer_table[2];
1298             pDst[2].set(ir + y2, ig + y2, ib + y2);
1299
1300             const int y3 = pInten_modifer_table[3];
1301             pDst[3].set(ir + y3, ig + y3, ib + y3);
1302
1303             return success;
1304         }
1305
1306         void etc1_block::get_abs_subblock_colors(color_quad_u8 *pDst, uint16 packed_color4, uint table_idx)
1307         {
1308             RG_ETC1_ASSERT(table_idx < cETC1IntenModifierValues);
1309             const int *pInten_modifer_table = &g_etc1_inten_tables[table_idx][0];
1310
1311             uint r, g, b;
1312             unpack_color4(r, g, b, packed_color4, true);
1313
1314             const int ir = static_cast<int>(r), ig = static_cast<int>(g), ib = static_cast<int>(b);
1315
1316             const int y0 = pInten_modifer_table[0];
1317             pDst[0].set(ir + y0, ig + y0, ib + y0);
1318
1319             const int y1 = pInten_modifer_table[1];
1320             pDst[1].set(ir + y1, ig + y1, ib + y1);
1321
1322             const int y2 = pInten_modifer_table[2];
1323             pDst[2].set(ir + y2, ig + y2, ib + y2);
1324
1325             const int y3 = pInten_modifer_table[3];
1326             pDst[3].set(ir + y3, ig + y3, ib + y3);
1327         }
1328
1329         bool unpack_etc1_block(const void *pETC1_block, unsigned int *pDst_pixels_rgba, bool preserve_alpha)
1330         {
1331             color_quad_u8 *pDst = reinterpret_cast<color_quad_u8 *>(pDst_pixels_rgba);
1332             const etc1_block &block = *static_cast<const etc1_block *>(pETC1_block);
1333
1334             const bool diff_flag = block.get_diff_bit();
1335             const bool flip_flag = block.get_flip_bit();
1336             const uint table_index0 = block.get_inten_table(0);
1337             const uint table_index1 = block.get_inten_table(1);
1338
1339             color_quad_u8 subblock_colors0[4];
1340             color_quad_u8 subblock_colors1[4];
1341             bool success = true;
1342
1343             if (diff_flag)
1344             {
1345                 const uint16 base_color5 = block.get_base5_color();
1346                 const uint16 delta_color3 = block.get_delta3_color();
1347                 etc1_block::get_diff_subblock_colors(subblock_colors0, base_color5, table_index0);
1348
1349                 if (!etc1_block::get_diff_subblock_colors(subblock_colors1, base_color5, delta_color3, table_index1))
1350                     success = false;
1351             }
1352             else
1353             {
1354                 const uint16 base_color4_0 = block.get_base4_color(0);
1355                 etc1_block::get_abs_subblock_colors(subblock_colors0, base_color4_0, table_index0);
1356
1357                 const uint16 base_color4_1 = block.get_base4_color(1);
1358                 etc1_block::get_abs_subblock_colors(subblock_colors1, base_color4_1, table_index1);
1359             }
1360
1361             if (preserve_alpha)
1362             {
1363                 if (flip_flag)
1364                 {
1365                     for (uint y = 0; y < 2; y++)
1366                     {
1367                         pDst[0].set_rgb(subblock_colors0[block.get_selector(0, y)]);
1368                         pDst[1].set_rgb(subblock_colors0[block.get_selector(1, y)]);
1369                         pDst[2].set_rgb(subblock_colors0[block.get_selector(2, y)]);
1370                         pDst[3].set_rgb(subblock_colors0[block.get_selector(3, y)]);
1371                         pDst += 4;
1372                     }
1373
1374                     for (uint y = 2; y < 4; y++)
1375                     {
1376                         pDst[0].set_rgb(subblock_colors1[block.get_selector(0, y)]);
1377                         pDst[1].set_rgb(subblock_colors1[block.get_selector(1, y)]);
1378                         pDst[2].set_rgb(subblock_colors1[block.get_selector(2, y)]);
1379                         pDst[3].set_rgb(subblock_colors1[block.get_selector(3, y)]);
1380                         pDst += 4;
1381                     }
1382                 }
1383                 else
1384                 {
1385                     for (uint y = 0; y < 4; y++)
1386                     {
1387                         pDst[0].set_rgb(subblock_colors0[block.get_selector(0, y)]);
1388                         pDst[1].set_rgb(subblock_colors0[block.get_selector(1, y)]);
1389                         pDst[2].set_rgb(subblock_colors1[block.get_selector(2, y)]);
1390                         pDst[3].set_rgb(subblock_colors1[block.get_selector(3, y)]);
1391                         pDst += 4;
1392                     }
1393                 }
1394             }
1395             else
1396             {
1397                 if (flip_flag)
1398                 {
1399                     // 0000
1400                     // 0000
1401                     // 1111
1402                     // 1111
1403                     for (uint y = 0; y < 2; y++)
1404                     {
1405                         pDst[0] = subblock_colors0[block.get_selector(0, y)];
1406                         pDst[1] = subblock_colors0[block.get_selector(1, y)];
1407                         pDst[2] = subblock_colors0[block.get_selector(2, y)];
1408                         pDst[3] = subblock_colors0[block.get_selector(3, y)];
1409                         pDst += 4;
1410                     }
1411
1412                     for (uint y = 2; y < 4; y++)
1413                     {
1414                         pDst[0] = subblock_colors1[block.get_selector(0, y)];
1415                         pDst[1] = subblock_colors1[block.get_selector(1, y)];
1416                         pDst[2] = subblock_colors1[block.get_selector(2, y)];
1417                         pDst[3] = subblock_colors1[block.get_selector(3, y)];
1418                         pDst += 4;
1419                     }
1420                 }
1421                 else
1422                 {
1423                     // 0011
1424                     // 0011
1425                     // 0011
1426                     // 0011
1427                     for (uint y = 0; y < 4; y++)
1428                     {
1429                         pDst[0] = subblock_colors0[block.get_selector(0, y)];
1430                         pDst[1] = subblock_colors0[block.get_selector(1, y)];
1431                         pDst[2] = subblock_colors1[block.get_selector(2, y)];
1432                         pDst[3] = subblock_colors1[block.get_selector(3, y)];
1433                         pDst += 4;
1434                     }
1435                 }
1436             }
1437
1438             return success;
1439         }
1440
1441         struct etc1_solution_coordinates
1442         {
1443             inline etc1_solution_coordinates()
1444                 : m_unscaled_color(0, 0, 0, 0),
1445                   m_inten_table(0),
1446                   m_color4(false)
1447             {
1448             }
1449
1450             inline etc1_solution_coordinates(uint r, uint g, uint b, uint inten_table, bool color4)
1451                 : m_unscaled_color(r, g, b, 255),
1452                   m_inten_table(inten_table),
1453                   m_color4(color4)
1454             {
1455             }
1456
1457             inline etc1_solution_coordinates(const color_quad_u8 &c, uint inten_table, bool color4)
1458                 : m_unscaled_color(c),
1459                   m_inten_table(inten_table),
1460                   m_color4(color4)
1461             {
1462             }
1463
1464             inline etc1_solution_coordinates(const etc1_solution_coordinates &other)
1465             {
1466                 *this = other;
1467             }
1468
1469             inline etc1_solution_coordinates &operator=(const etc1_solution_coordinates &rhs)
1470             {
1471                 m_unscaled_color = rhs.m_unscaled_color;
1472                 m_inten_table = rhs.m_inten_table;
1473                 m_color4 = rhs.m_color4;
1474                 return *this;
1475             }
1476
1477             inline void clear()
1478             {
1479                 m_unscaled_color.clear();
1480                 m_inten_table = 0;
1481                 m_color4 = false;
1482             }
1483
1484             inline color_quad_u8 get_scaled_color() const
1485             {
1486                 int br, bg, bb;
1487                 if (m_color4)
1488                 {
1489                     br = m_unscaled_color.r | (m_unscaled_color.r << 4);
1490                     bg = m_unscaled_color.g | (m_unscaled_color.g << 4);
1491                     bb = m_unscaled_color.b | (m_unscaled_color.b << 4);
1492                 }
1493                 else
1494                 {
1495                     br = (m_unscaled_color.r >> 2) | (m_unscaled_color.r << 3);
1496                     bg = (m_unscaled_color.g >> 2) | (m_unscaled_color.g << 3);
1497                     bb = (m_unscaled_color.b >> 2) | (m_unscaled_color.b << 3);
1498                 }
1499                 return color_quad_u8(br, bg, bb);
1500             }
1501
1502             inline void get_block_colors(color_quad_u8 *pBlock_colors)
1503             {
1504                 int br, bg, bb;
1505                 if (m_color4)
1506                 {
1507                     br = m_unscaled_color.r | (m_unscaled_color.r << 4);
1508                     bg = m_unscaled_color.g | (m_unscaled_color.g << 4);
1509                     bb = m_unscaled_color.b | (m_unscaled_color.b << 4);
1510                 }
1511                 else
1512                 {
1513                     br = (m_unscaled_color.r >> 2) | (m_unscaled_color.r << 3);
1514                     bg = (m_unscaled_color.g >> 2) | (m_unscaled_color.g << 3);
1515                     bb = (m_unscaled_color.b >> 2) | (m_unscaled_color.b << 3);
1516                 }
1517                 const int *pInten_table = g_etc1_inten_tables[m_inten_table];
1518                 pBlock_colors[0].set(br + pInten_table[0], bg + pInten_table[0], bb + pInten_table[0]);
1519                 pBlock_colors[1].set(br + pInten_table[1], bg + pInten_table[1], bb + pInten_table[1]);
1520                 pBlock_colors[2].set(br + pInten_table[2], bg + pInten_table[2], bb + pInten_table[2]);
1521                 pBlock_colors[3].set(br + pInten_table[3], bg + pInten_table[3], bb + pInten_table[3]);
1522             }
1523
1524             color_quad_u8 m_unscaled_color;
1525             uint m_inten_table;
1526             bool m_color4;
1527         };
1528
1529         class etc1_optimizer
1530         {
1531             etc1_optimizer(const etc1_optimizer &);
1532             etc1_optimizer &operator=(const etc1_optimizer &);
1533
1534         public:
1535             etc1_optimizer()
1536             {
1537                 clear();
1538             }
1539
1540             void clear()
1541             {
1542                 m_pParams = NULL;
1543                 m_pResult = NULL;
1544                 m_pSorted_luma = NULL;
1545                 m_pSorted_luma_indices = NULL;
1546             }
1547
1548             struct params : etc1_pack_params
1549             {
1550                 params()
1551                 {
1552                     clear();
1553                 }
1554
1555                 params(const etc1_pack_params &base_params)
1556                     : etc1_pack_params(base_params)
1557                 {
1558                     clear_optimizer_params();
1559                 }
1560
1561                 void clear()
1562                 {
1563                     etc1_pack_params::clear();
1564                     clear_optimizer_params();
1565                 }
1566
1567                 void clear_optimizer_params()
1568                 {
1569                     m_num_src_pixels = 0;
1570                     m_pSrc_pixels = 0;
1571
1572                     m_use_color4 = false;
1573                     static const int s_default_scan_delta[] = { 0 };
1574                     m_pScan_deltas = s_default_scan_delta;
1575                     m_scan_delta_size = 1;
1576
1577                     m_base_color5.clear();
1578                     m_constrain_against_base_color5 = false;
1579                 }
1580
1581                 uint m_num_src_pixels;
1582                 const color_quad_u8 *m_pSrc_pixels;
1583
1584                 bool m_use_color4;
1585                 const int *m_pScan_deltas;
1586                 uint m_scan_delta_size;
1587
1588                 color_quad_u8 m_base_color5;
1589                 bool m_constrain_against_base_color5;
1590             };
1591
1592             struct results
1593             {
1594                 uint64_t m_error;
1595                 color_quad_u8 m_block_color_unscaled;
1596                 uint m_block_inten_table;
1597                 uint m_n;
1598                 uint8 *m_pSelectors;
1599                 bool m_block_color4;
1600
1601                 inline results &operator=(const results &rhs)
1602                 {
1603                     m_block_color_unscaled = rhs.m_block_color_unscaled;
1604                     m_block_color4 = rhs.m_block_color4;
1605                     m_block_inten_table = rhs.m_block_inten_table;
1606                     m_error = rhs.m_error;
1607                     RG_ETC1_ASSERT(m_n == rhs.m_n);
1608                     memcpy(m_pSelectors, rhs.m_pSelectors, rhs.m_n);
1609                     return *this;
1610                 }
1611             };
1612
1613             void init(const params &params, results &result);
1614             bool compute();
1615
1616         private:
1617             struct potential_solution
1618             {
1619                 potential_solution()
1620                     : m_coords(), m_error(cUINT64_MAX), m_valid(false)
1621                 {
1622                 }
1623
1624                 etc1_solution_coordinates m_coords;
1625                 uint8 m_selectors[8];
1626                 uint64_t m_error;
1627                 bool m_valid;
1628
1629                 void clear()
1630                 {
1631                     m_coords.clear();
1632                     m_error = cUINT64_MAX;
1633                     m_valid = false;
1634                 }
1635             };
1636
1637             const params *m_pParams;
1638             results *m_pResult;
1639
1640             int m_limit;
1641
1642             vec3F m_avg_color;
1643             int m_br, m_bg, m_bb;
1644             uint16 m_luma[8];
1645             uint32 m_sorted_luma[2][8];
1646             const uint32 *m_pSorted_luma_indices;
1647             uint32 *m_pSorted_luma;
1648
1649             uint8 m_selectors[8];
1650             uint8 m_best_selectors[8];
1651
1652             potential_solution m_best_solution;
1653             potential_solution m_trial_solution;
1654             uint8 m_temp_selectors[8];
1655
1656             bool evaluate_solution(const etc1_solution_coordinates &coords, potential_solution &trial_solution, potential_solution *pBest_solution);
1657             bool evaluate_solution_fast(const etc1_solution_coordinates &coords, potential_solution &trial_solution, potential_solution *pBest_solution);
1658         };
1659
1660         bool etc1_optimizer::compute()
1661         {
1662             const uint n = m_pParams->m_num_src_pixels;
1663             const int scan_delta_size = m_pParams->m_scan_delta_size;
1664
1665             // Scan through a subset of the 3D lattice centered around the avg block color trying each 3D (555 or 444) lattice point as a potential block color.
1666             // Each time a better solution is found try to refine the current solution's block color based of the current selectors and intensity table index.
1667             for (int zdi = 0; zdi < scan_delta_size; zdi++)
1668             {
1669                 const int zd = m_pParams->m_pScan_deltas[zdi];
1670                 const int mbb = m_bb + zd;
1671                 if (mbb < 0)
1672                     continue;
1673                 else if (mbb > m_limit)
1674                     break;
1675
1676                 for (int ydi = 0; ydi < scan_delta_size; ydi++)
1677                 {
1678                     const int yd = m_pParams->m_pScan_deltas[ydi];
1679                     const int mbg = m_bg + yd;
1680                     if (mbg < 0)
1681                         continue;
1682                     else if (mbg > m_limit)
1683                         break;
1684
1685                     for (int xdi = 0; xdi < scan_delta_size; xdi++)
1686                     {
1687                         const int xd = m_pParams->m_pScan_deltas[xdi];
1688                         const int mbr = m_br + xd;
1689                         if (mbr < 0)
1690                             continue;
1691                         else if (mbr > m_limit)
1692                             break;
1693
1694                         etc1_solution_coordinates coords(mbr, mbg, mbb, 0, m_pParams->m_use_color4);
1695                         if (m_pParams->m_quality == cHighQuality)
1696                         {
1697                             if (!evaluate_solution(coords, m_trial_solution, &m_best_solution))
1698                                 continue;
1699                         }
1700                         else
1701                         {
1702                             if (!evaluate_solution_fast(coords, m_trial_solution, &m_best_solution))
1703                                 continue;
1704                         }
1705
1706                         // Now we have the input block, the avg. color of the input pixels, a set of trial selector indices, and the block color+intensity index.
1707                         // Now, for each component, attempt to refine the current solution by solving a simple linear equation. For example, for 4 colors:
1708                         // The goal is:
1709                         // pixel0 - (block_color+inten_table[selector0]) + pixel1 - (block_color+inten_table[selector1]) + pixel2 - (block_color+inten_table[selector2]) + pixel3 - (block_color+inten_table[selector3]) = 0
1710                         // Rearranging this:
1711                         // (pixel0 + pixel1 + pixel2 + pixel3) - (block_color+inten_table[selector0]) - (block_color+inten_table[selector1]) - (block_color+inten_table[selector2]) - (block_color+inten_table[selector3]) = 0
1712                         // (pixel0 + pixel1 + pixel2 + pixel3) - block_color - inten_table[selector0] - block_color-inten_table[selector1] - block_color-inten_table[selector2] - block_color-inten_table[selector3] = 0
1713                         // (pixel0 + pixel1 + pixel2 + pixel3) - 4*block_color - inten_table[selector0] - inten_table[selector1] - inten_table[selector2] - inten_table[selector3] = 0
1714                         // (pixel0 + pixel1 + pixel2 + pixel3) - 4*block_color - (inten_table[selector0] + inten_table[selector1] + inten_table[selector2] + inten_table[selector3]) = 0
1715                         // (pixel0 + pixel1 + pixel2 + pixel3)/4 - block_color - (inten_table[selector0] + inten_table[selector1] + inten_table[selector2] + inten_table[selector3])/4 = 0
1716                         // block_color = (pixel0 + pixel1 + pixel2 + pixel3)/4 - (inten_table[selector0] + inten_table[selector1] + inten_table[selector2] + inten_table[selector3])/4
1717                         // So what this means:
1718                         // optimal_block_color = avg_input - avg_inten_delta
1719                         // So the optimal block color can be computed by taking the average block color and subtracting the current average of the intensity delta.
1720                         // Unfortunately, optimal_block_color must then be quantized to 555 or 444 so it's not always possible to improve matters using this formula.
1721                         // Also, the above formula is for unclamped intensity deltas. The actual implementation takes into account clamping.
1722
1723                         const uint max_refinement_trials = (m_pParams->m_quality == cLowQuality) ? 2 : (((xd | yd | zd) == 0) ? 4 : 2);
1724                         for (uint refinement_trial = 0; refinement_trial < max_refinement_trials; refinement_trial++)
1725                         {
1726                             const uint8 *pSelectors = m_best_solution.m_selectors;
1727                             const int *pInten_table = g_etc1_inten_tables[m_best_solution.m_coords.m_inten_table];
1728
1729                             int delta_sum_r = 0, delta_sum_g = 0, delta_sum_b = 0;
1730                             const color_quad_u8 base_color(m_best_solution.m_coords.get_scaled_color());
1731                             for (uint r = 0; r < n; r++)
1732                             {
1733                                 const uint s = *pSelectors++;
1734                                 const int yd = pInten_table[s];
1735                                 // Compute actual delta being applied to each pixel, taking into account clamping.
1736                                 delta_sum_r += rg_etc1::clamp<int>(base_color.r + yd, 0, 255) - base_color.r;
1737                                 delta_sum_g += rg_etc1::clamp<int>(base_color.g + yd, 0, 255) - base_color.g;
1738                                 delta_sum_b += rg_etc1::clamp<int>(base_color.b + yd, 0, 255) - base_color.b;
1739                             }
1740                             if ((!delta_sum_r) && (!delta_sum_g) && (!delta_sum_b))
1741                                 break;
1742                             const float avg_delta_r_f = static_cast<float>(delta_sum_r) / n;
1743                             const float avg_delta_g_f = static_cast<float>(delta_sum_g) / n;
1744                             const float avg_delta_b_f = static_cast<float>(delta_sum_b) / n;
1745                             const int br1 = rg_etc1::clamp<int>(static_cast<uint>((m_avg_color[0] - avg_delta_r_f) * m_limit / 255.0f + .5f), 0, m_limit);
1746                             const int bg1 = rg_etc1::clamp<int>(static_cast<uint>((m_avg_color[1] - avg_delta_g_f) * m_limit / 255.0f + .5f), 0, m_limit);
1747                             const int bb1 = rg_etc1::clamp<int>(static_cast<uint>((m_avg_color[2] - avg_delta_b_f) * m_limit / 255.0f + .5f), 0, m_limit);
1748
1749                             bool skip = false;
1750
1751                             if ((mbr == br1) && (mbg == bg1) && (mbb == bb1))
1752                                 skip = true;
1753                             else if ((br1 == m_best_solution.m_coords.m_unscaled_color.r) && (bg1 == m_best_solution.m_coords.m_unscaled_color.g) && (bb1 == m_best_solution.m_coords.m_unscaled_color.b))
1754                                 skip = true;
1755                             else if ((m_br == br1) && (m_bg == bg1) && (m_bb == bb1))
1756                                 skip = true;
1757
1758                             if (skip)
1759                                 break;
1760
1761                             etc1_solution_coordinates coords1(br1, bg1, bb1, 0, m_pParams->m_use_color4);
1762                             if (m_pParams->m_quality == cHighQuality)
1763                             {
1764                                 if (!evaluate_solution(coords1, m_trial_solution, &m_best_solution))
1765                                     break;
1766                             }
1767                             else
1768                             {
1769                                 if (!evaluate_solution_fast(coords1, m_trial_solution, &m_best_solution))
1770                                     break;
1771                             }
1772
1773                         } // refinement_trial
1774
1775                     } // xdi
1776                 }     // ydi
1777             }         // zdi
1778
1779             if (!m_best_solution.m_valid)
1780             {
1781                 m_pResult->m_error = cUINT32_MAX;
1782                 return false;
1783             }
1784
1785             const uint8 *pSelectors = m_best_solution.m_selectors;
1786
1787 #ifdef RG_ETC1_BUILD_DEBUG
1788             {
1789                 color_quad_u8 block_colors[4];
1790                 m_best_solution.m_coords.get_block_colors(block_colors);
1791
1792                 const color_quad_u8 *pSrc_pixels = m_pParams->m_pSrc_pixels;
1793                 uint64_t actual_error = 0;
1794                 for (uint i = 0; i < n; i++)
1795                     actual_error += pSrc_pixels[i].squared_distance_rgb(block_colors[pSelectors[i]]);
1796
1797                 RG_ETC1_ASSERT(actual_error == m_best_solution.m_error);
1798             }
1799 #endif
1800
1801             m_pResult->m_error = m_best_solution.m_error;
1802
1803             m_pResult->m_block_color_unscaled = m_best_solution.m_coords.m_unscaled_color;
1804             m_pResult->m_block_color4 = m_best_solution.m_coords.m_color4;
1805
1806             m_pResult->m_block_inten_table = m_best_solution.m_coords.m_inten_table;
1807             memcpy(m_pResult->m_pSelectors, pSelectors, n);
1808             m_pResult->m_n = n;
1809
1810             return true;
1811         }
1812
1813         void etc1_optimizer::init(const params &p, results &r)
1814         {
1815             // This version is hardcoded for 8 pixel subblocks.
1816             RG_ETC1_ASSERT(p.m_num_src_pixels == 8);
1817
1818             m_pParams = &p;
1819             m_pResult = &r;
1820
1821             const uint n = 8;
1822
1823             m_limit = m_pParams->m_use_color4 ? 15 : 31;
1824
1825             vec3F avg_color(0.0f);
1826
1827             for (uint i = 0; i < n; i++)
1828             {
1829                 const color_quad_u8 &c = m_pParams->m_pSrc_pixels[i];
1830                 const vec3F fc(c.r, c.g, c.b);
1831
1832                 avg_color += fc;
1833
1834                 m_luma[i] = static_cast<uint16>(c.r + c.g + c.b);
1835                 m_sorted_luma[0][i] = i;
1836             }
1837             avg_color *= (1.0f / static_cast<float>(n));
1838             m_avg_color = avg_color;
1839
1840             m_br = rg_etc1::clamp<int>(static_cast<uint>(m_avg_color[0] * m_limit / 255.0f + .5f), 0, m_limit);
1841             m_bg = rg_etc1::clamp<int>(static_cast<uint>(m_avg_color[1] * m_limit / 255.0f + .5f), 0, m_limit);
1842             m_bb = rg_etc1::clamp<int>(static_cast<uint>(m_avg_color[2] * m_limit / 255.0f + .5f), 0, m_limit);
1843
1844             if (m_pParams->m_quality <= cMediumQuality)
1845             {
1846                 m_pSorted_luma_indices = indirect_radix_sort(n, m_sorted_luma[0], m_sorted_luma[1], m_luma, 0, sizeof(m_luma[0]), false);
1847                 m_pSorted_luma = m_sorted_luma[0];
1848                 if (m_pSorted_luma_indices == m_sorted_luma[0])
1849                     m_pSorted_luma = m_sorted_luma[1];
1850
1851                 for (uint i = 0; i < n; i++)
1852                     m_pSorted_luma[i] = m_luma[m_pSorted_luma_indices[i]];
1853             }
1854
1855             m_best_solution.m_coords.clear();
1856             m_best_solution.m_valid = false;
1857             m_best_solution.m_error = cUINT64_MAX;
1858         }
1859
1860         bool etc1_optimizer::evaluate_solution(const etc1_solution_coordinates &coords, potential_solution &trial_solution, potential_solution *pBest_solution)
1861         {
1862             trial_solution.m_valid = false;
1863
1864             if (m_pParams->m_constrain_against_base_color5)
1865             {
1866                 const int dr = coords.m_unscaled_color.r - m_pParams->m_base_color5.r;
1867                 const int dg = coords.m_unscaled_color.g - m_pParams->m_base_color5.g;
1868                 const int db = coords.m_unscaled_color.b - m_pParams->m_base_color5.b;
1869
1870                 if ((rg_etc1::minimum(dr, dg, db) < cETC1ColorDeltaMin) || (rg_etc1::maximum(dr, dg, db) > cETC1ColorDeltaMax))
1871                     return false;
1872             }
1873
1874             const color_quad_u8 base_color(coords.get_scaled_color());
1875
1876             const uint n = 8;
1877
1878             trial_solution.m_error = cUINT64_MAX;
1879
1880             for (uint inten_table = 0; inten_table < cETC1IntenModifierValues; inten_table++)
1881             {
1882                 const int *pInten_table = g_etc1_inten_tables[inten_table];
1883
1884                 color_quad_u8 block_colors[4];
1885                 for (uint s = 0; s < 4; s++)
1886                 {
1887                     const int yd = pInten_table[s];
1888                     block_colors[s].set(base_color.r + yd, base_color.g + yd, base_color.b + yd, 0);
1889                 }
1890
1891                 uint64_t total_error = 0;
1892
1893                 const color_quad_u8 *pSrc_pixels = m_pParams->m_pSrc_pixels;
1894                 for (uint c = 0; c < n; c++)
1895                 {
1896                     const color_quad_u8 &src_pixel = *pSrc_pixels++;
1897
1898                     uint best_selector_index = 0;
1899                     uint best_error = rg_etc1::square(src_pixel.r - block_colors[0].r) + rg_etc1::square(src_pixel.g - block_colors[0].g) + rg_etc1::square(src_pixel.b - block_colors[0].b);
1900
1901                     uint trial_error = rg_etc1::square(src_pixel.r - block_colors[1].r) + rg_etc1::square(src_pixel.g - block_colors[1].g) + rg_etc1::square(src_pixel.b - block_colors[1].b);
1902                     if (trial_error < best_error)
1903                     {
1904                         best_error = trial_error;
1905                         best_selector_index = 1;
1906                     }
1907
1908                     trial_error = rg_etc1::square(src_pixel.r - block_colors[2].r) + rg_etc1::square(src_pixel.g - block_colors[2].g) + rg_etc1::square(src_pixel.b - block_colors[2].b);
1909                     if (trial_error < best_error)
1910                     {
1911                         best_error = trial_error;
1912                         best_selector_index = 2;
1913                     }
1914
1915                     trial_error = rg_etc1::square(src_pixel.r - block_colors[3].r) + rg_etc1::square(src_pixel.g - block_colors[3].g) + rg_etc1::square(src_pixel.b - block_colors[3].b);
1916                     if (trial_error < best_error)
1917                     {
1918                         best_error = trial_error;
1919                         best_selector_index = 3;
1920                     }
1921
1922                     m_temp_selectors[c] = static_cast<uint8>(best_selector_index);
1923
1924                     total_error += best_error;
1925                     if (total_error >= trial_solution.m_error)
1926                         break;
1927                 }
1928
1929                 if (total_error < trial_solution.m_error)
1930                 {
1931                     trial_solution.m_error = total_error;
1932                     trial_solution.m_coords.m_inten_table = inten_table;
1933                     memcpy(trial_solution.m_selectors, m_temp_selectors, 8);
1934                     trial_solution.m_valid = true;
1935                 }
1936             }
1937             trial_solution.m_coords.m_unscaled_color = coords.m_unscaled_color;
1938             trial_solution.m_coords.m_color4 = m_pParams->m_use_color4;
1939
1940             bool success = false;
1941             if (pBest_solution)
1942             {
1943                 if (trial_solution.m_error < pBest_solution->m_error)
1944                 {
1945                     *pBest_solution = trial_solution;
1946                     success = true;
1947                 }
1948             }
1949
1950             return success;
1951         }
1952
1953         bool etc1_optimizer::evaluate_solution_fast(const etc1_solution_coordinates &coords, potential_solution &trial_solution, potential_solution *pBest_solution)
1954         {
1955             if (m_pParams->m_constrain_against_base_color5)
1956             {
1957                 const int dr = coords.m_unscaled_color.r - m_pParams->m_base_color5.r;
1958                 const int dg = coords.m_unscaled_color.g - m_pParams->m_base_color5.g;
1959                 const int db = coords.m_unscaled_color.b - m_pParams->m_base_color5.b;
1960
1961                 if ((rg_etc1::minimum(dr, dg, db) < cETC1ColorDeltaMin) || (rg_etc1::maximum(dr, dg, db) > cETC1ColorDeltaMax))
1962                 {
1963                     trial_solution.m_valid = false;
1964                     return false;
1965                 }
1966             }
1967
1968             const color_quad_u8 base_color(coords.get_scaled_color());
1969
1970             const uint n = 8;
1971
1972             trial_solution.m_error = cUINT64_MAX;
1973
1974             for (int inten_table = cETC1IntenModifierValues - 1; inten_table >= 0; --inten_table)
1975             {
1976                 const int *pInten_table = g_etc1_inten_tables[inten_table];
1977
1978                 uint block_inten[4];
1979                 color_quad_u8 block_colors[4];
1980                 for (uint s = 0; s < 4; s++)
1981                 {
1982                     const int yd = pInten_table[s];
1983                     color_quad_u8 block_color(base_color.r + yd, base_color.g + yd, base_color.b + yd, 0);
1984                     block_colors[s] = block_color;
1985                     block_inten[s] = block_color.r + block_color.g + block_color.b;
1986                 }
1987
1988                 // evaluate_solution_fast() enforces/assumesd a total ordering of the input colors along the intensity (1,1,1) axis to more quickly classify the inputs to selectors.
1989                 // The inputs colors have been presorted along the projection onto this axis, and ETC1 block colors are always ordered along the intensity axis, so this classification is fast.
1990                 // 0   1   2   3
1991                 //   01  12  23
1992                 const uint block_inten_midpoints[3] = { block_inten[0] + block_inten[1], block_inten[1] + block_inten[2], block_inten[2] + block_inten[3] };
1993
1994                 uint64_t total_error = 0;
1995                 const color_quad_u8 *pSrc_pixels = m_pParams->m_pSrc_pixels;
1996                 if ((m_pSorted_luma[n - 1] * 2) < block_inten_midpoints[0])
1997                 {
1998                     if (block_inten[0] > m_pSorted_luma[n - 1])
1999                     {
2000                         const uint min_error = static_cast<uint>(labs(block_inten[0] - m_pSorted_luma[n - 1]));
2001                         if (min_error >= trial_solution.m_error)
2002                             continue;
2003                     }
2004
2005                     memset(&m_temp_selectors[0], 0, n);
2006
2007                     for (uint c = 0; c < n; c++)
2008                         total_error += block_colors[0].squared_distance_rgb(pSrc_pixels[c]);
2009                 }
2010                 else if ((m_pSorted_luma[0] * 2) >= block_inten_midpoints[2])
2011                 {
2012                     if (m_pSorted_luma[0] > block_inten[3])
2013                     {
2014                         const uint min_error = static_cast<uint>(labs(m_pSorted_luma[0] - block_inten[3]));
2015                         if (min_error >= trial_solution.m_error)
2016                             continue;
2017                     }
2018
2019                     memset(&m_temp_selectors[0], 3, n);
2020
2021                     for (uint c = 0; c < n; c++)
2022                         total_error += block_colors[3].squared_distance_rgb(pSrc_pixels[c]);
2023                 }
2024                 else
2025                 {
2026                     uint cur_selector = 0, c;
2027                     for (c = 0; c < n; c++)
2028                     {
2029                         const uint y = m_pSorted_luma[c];
2030                         while ((y * 2) >= block_inten_midpoints[cur_selector])
2031                             if (++cur_selector > 2)
2032                                 goto done;
2033                         const uint sorted_pixel_index = m_pSorted_luma_indices[c];
2034                         m_temp_selectors[sorted_pixel_index] = static_cast<uint8>(cur_selector);
2035                         total_error += block_colors[cur_selector].squared_distance_rgb(pSrc_pixels[sorted_pixel_index]);
2036                     }
2037                 done:
2038                     while (c < n)
2039                     {
2040                         const uint sorted_pixel_index = m_pSorted_luma_indices[c];
2041                         m_temp_selectors[sorted_pixel_index] = 3;
2042                         total_error += block_colors[3].squared_distance_rgb(pSrc_pixels[sorted_pixel_index]);
2043                         ++c;
2044                     }
2045                 }
2046
2047                 if (total_error < trial_solution.m_error)
2048                 {
2049                     trial_solution.m_error = total_error;
2050                     trial_solution.m_coords.m_inten_table = inten_table;
2051                     memcpy(trial_solution.m_selectors, m_temp_selectors, n);
2052                     trial_solution.m_valid = true;
2053                     if (!total_error)
2054                         break;
2055                 }
2056             }
2057             trial_solution.m_coords.m_unscaled_color = coords.m_unscaled_color;
2058             trial_solution.m_coords.m_color4 = m_pParams->m_use_color4;
2059
2060             bool success = false;
2061             if (pBest_solution)
2062             {
2063                 if (trial_solution.m_error < pBest_solution->m_error)
2064                 {
2065                     *pBest_solution = trial_solution;
2066                     success = true;
2067                 }
2068             }
2069
2070             return success;
2071         }
2072
2073         static uint etc1_decode_value(uint diff, uint inten, uint selector, uint packed_c)
2074         {
2075             const uint limit = diff ? 32 : 16;
2076             VOGL_NOTE_UNUSED(limit);
2077             RG_ETC1_ASSERT((diff < 2) && (inten < 8) && (selector < 4) && (packed_c < limit));
2078             int c;
2079             if (diff)
2080                 c = (packed_c >> 2) | (packed_c << 3);
2081             else
2082                 c = packed_c | (packed_c << 4);
2083             c += g_etc1_inten_tables[inten][selector];
2084             c = rg_etc1::clamp<int>(c, 0, 255);
2085             return c;
2086         }
2087
2088         static inline int mul_8bit(int a, int b)
2089         {
2090             int t = a * b + 128;
2091             return (t + (t >> 8)) >> 8;
2092         }
2093
2094         void pack_etc1_block_init()
2095         {
2096             for (uint diff = 0; diff < 2; diff++)
2097             {
2098                 const uint limit = diff ? 32 : 16;
2099
2100                 for (uint inten = 0; inten < 8; inten++)
2101                 {
2102                     for (uint selector = 0; selector < 4; selector++)
2103                     {
2104                         const uint inverse_table_index = diff + (inten << 1) + (selector << 4);
2105                         for (uint color = 0; color < 256; color++)
2106                         {
2107                             uint best_error = cUINT32_MAX, best_packed_c = 0;
2108                             for (uint packed_c = 0; packed_c < limit; packed_c++)
2109                             {
2110                                 int v = etc1_decode_value(diff, inten, selector, packed_c);
2111                                 uint err = static_cast<uint>(labs(v - static_cast<int>(color)));
2112                                 if (err < best_error)
2113                                 {
2114                                     best_error = err;
2115                                     best_packed_c = packed_c;
2116                                     if (!best_error)
2117                                         break;
2118                                 }
2119                             }
2120                             RG_ETC1_ASSERT(best_error <= 255);
2121                             g_etc1_inverse_lookup[inverse_table_index][color] = static_cast<uint16>(best_packed_c | (best_error << 8));
2122                         }
2123                     }
2124                 }
2125             }
2126
2127             uint expand5[32];
2128             for (int i = 0; i < 32; i++)
2129                 expand5[i] = (i << 3) | (i >> 2);
2130
2131             for (int i = 0; i < 256 + 16; i++)
2132             {
2133                 int v = clamp<int>(i - 8, 0, 255);
2134                 g_quant5_tab[i] = static_cast<uint8>(expand5[mul_8bit(v, 31)]);
2135             }
2136         }
2137
2138         // Packs solid color blocks efficiently using a set of small precomputed tables.
2139         // For random 888 inputs, MSE results are better than Erricson's ETC1 packer in "slow" mode ~9.5% of the time, is slightly worse only ~.01% of the time, and is equal the rest of the time.
2140         static uint64_t pack_etc1_block_solid_color(etc1_block &block, const uint8 *pColor, etc1_pack_params &pack_params)
2141         {
2142             VOGL_NOTE_UNUSED(pack_params);
2143             RG_ETC1_ASSERT(g_etc1_inverse_lookup[0][255]);
2144
2145             static uint s_next_comp[4] = { 1, 2, 0, 1 };
2146
2147             uint best_error = cUINT32_MAX, best_i = 0;
2148             int best_x = 0, best_packed_c1 = 0, best_packed_c2 = 0;
2149
2150             // For each possible 8-bit value, there is a precomputed list of diff/inten/selector configurations that allow that 8-bit value to be encoded with no error.
2151             for (uint i = 0; i < 3; i++)
2152             {
2153                 const uint c1 = pColor[s_next_comp[i]], c2 = pColor[s_next_comp[i + 1]];
2154
2155                 const int delta_range = 1;
2156                 for (int delta = -delta_range; delta <= delta_range; delta++)
2157                 {
2158                     const int c_plus_delta = rg_etc1::clamp<int>(pColor[i] + delta, 0, 255);
2159
2160                     const uint16 *pTable;
2161                     if (!c_plus_delta)
2162                         pTable = g_color8_to_etc_block_config_0_255[0];
2163                     else if (c_plus_delta == 255)
2164                         pTable = g_color8_to_etc_block_config_0_255[1];
2165                     else
2166                         pTable = g_color8_to_etc_block_config_1_to_254[c_plus_delta - 1];
2167
2168                     do
2169                     {
2170                         const uint x = *pTable++;
2171
2172 #ifdef RG_ETC1_BUILD_DEBUG
2173                         const uint diff = x & 1;
2174                         const uint inten = (x >> 1) & 7;
2175                         const uint selector = (x >> 4) & 3;
2176                         const uint p0 = (x >> 8) & 255;
2177                         RG_ETC1_ASSERT(etc1_decode_value(diff, inten, selector, p0) == (uint)c_plus_delta);
2178 #endif
2179
2180                         const uint16 *pInverse_table = g_etc1_inverse_lookup[x & 0xFF];
2181                         uint16 p1 = pInverse_table[c1];
2182                         uint16 p2 = pInverse_table[c2];
2183                         const uint trial_error = rg_etc1::square(c_plus_delta - pColor[i]) + rg_etc1::square(p1 >> 8) + rg_etc1::square(p2 >> 8);
2184                         if (trial_error < best_error)
2185                         {
2186                             best_error = trial_error;
2187                             best_x = x;
2188                             best_packed_c1 = p1 & 0xFF;
2189                             best_packed_c2 = p2 & 0xFF;
2190                             best_i = i;
2191                             if (!best_error)
2192                                 goto found_perfect_match;
2193                         }
2194                     } while (*pTable != 0xFFFF);
2195                 }
2196             }
2197         found_perfect_match:
2198
2199             const uint diff = best_x & 1;
2200             const uint inten = (best_x >> 1) & 7;
2201
2202             block.m_bytes[3] = static_cast<uint8>(((inten | (inten << 3)) << 2) | (diff << 1));
2203
2204             const uint etc1_selector = g_selector_index_to_etc1[(best_x >> 4) & 3];
2205             *reinterpret_cast<uint16 *>(&block.m_bytes[4]) = (etc1_selector & 2) ? 0xFFFF : 0;
2206             *reinterpret_cast<uint16 *>(&block.m_bytes[6]) = (etc1_selector & 1) ? 0xFFFF : 0;
2207
2208             const uint best_packed_c0 = (best_x >> 8) & 255;
2209             if (diff)
2210             {
2211                 block.m_bytes[best_i] = static_cast<uint8>(best_packed_c0 << 3);
2212                 block.m_bytes[s_next_comp[best_i]] = static_cast<uint8>(best_packed_c1 << 3);
2213                 block.m_bytes[s_next_comp[best_i + 1]] = static_cast<uint8>(best_packed_c2 << 3);
2214             }
2215             else
2216             {
2217                 block.m_bytes[best_i] = static_cast<uint8>(best_packed_c0 | (best_packed_c0 << 4));
2218                 block.m_bytes[s_next_comp[best_i]] = static_cast<uint8>(best_packed_c1 | (best_packed_c1 << 4));
2219                 block.m_bytes[s_next_comp[best_i + 1]] = static_cast<uint8>(best_packed_c2 | (best_packed_c2 << 4));
2220             }
2221
2222             return best_error;
2223         }
2224
2225         static uint pack_etc1_block_solid_color_constrained(
2226             etc1_optimizer::results &results,
2227             uint num_colors, const uint8 *pColor,
2228             etc1_pack_params &pack_params,
2229             bool use_diff,
2230             const color_quad_u8 *pBase_color5_unscaled)
2231         {
2232             RG_ETC1_ASSERT(g_etc1_inverse_lookup[0][255]);
2233
2234             VOGL_NOTE_UNUSED(pack_params);
2235             static uint s_next_comp[4] = { 1, 2, 0, 1 };
2236
2237             uint best_error = cUINT32_MAX, best_i = 0;
2238             int best_x = 0, best_packed_c1 = 0, best_packed_c2 = 0;
2239
2240             // For each possible 8-bit value, there is a precomputed list of diff/inten/selector configurations that allow that 8-bit value to be encoded with no error.
2241             for (uint i = 0; i < 3; i++)
2242             {
2243                 const uint c1 = pColor[s_next_comp[i]], c2 = pColor[s_next_comp[i + 1]];
2244
2245                 const int delta_range = 1;
2246                 for (int delta = -delta_range; delta <= delta_range; delta++)
2247                 {
2248                     const int c_plus_delta = rg_etc1::clamp<int>(pColor[i] + delta, 0, 255);
2249
2250                     const uint16 *pTable;
2251                     if (!c_plus_delta)
2252                         pTable = g_color8_to_etc_block_config_0_255[0];
2253                     else if (c_plus_delta == 255)
2254                         pTable = g_color8_to_etc_block_config_0_255[1];
2255                     else
2256                         pTable = g_color8_to_etc_block_config_1_to_254[c_plus_delta - 1];
2257
2258                     do
2259                     {
2260                         const uint x = *pTable++;
2261                         const uint diff = x & 1;
2262                         if (static_cast<uint>(use_diff) != diff)
2263                         {
2264                             if (*pTable == 0xFFFF)
2265                                 break;
2266                             continue;
2267                         }
2268
2269                         if ((diff) && (pBase_color5_unscaled))
2270                         {
2271                             const int p0 = (x >> 8) & 255;
2272                             int delta = p0 - static_cast<int>(pBase_color5_unscaled->c[i]);
2273                             if ((delta < cETC1ColorDeltaMin) || (delta > cETC1ColorDeltaMax))
2274                             {
2275                                 if (*pTable == 0xFFFF)
2276                                     break;
2277                                 continue;
2278                             }
2279                         }
2280
2281 #ifdef RG_ETC1_BUILD_DEBUG
2282                         {
2283                             const uint inten = (x >> 1) & 7;
2284                             const uint selector = (x >> 4) & 3;
2285                             const uint p0 = (x >> 8) & 255;
2286                             RG_ETC1_ASSERT(etc1_decode_value(diff, inten, selector, p0) == (uint)c_plus_delta);
2287                         }
2288 #endif
2289
2290                         const uint16 *pInverse_table = g_etc1_inverse_lookup[x & 0xFF];
2291                         uint16 p1 = pInverse_table[c1];
2292                         uint16 p2 = pInverse_table[c2];
2293
2294                         if ((diff) && (pBase_color5_unscaled))
2295                         {
2296                             int delta1 = (p1 & 0xFF) - static_cast<int>(pBase_color5_unscaled->c[s_next_comp[i]]);
2297                             int delta2 = (p2 & 0xFF) - static_cast<int>(pBase_color5_unscaled->c[s_next_comp[i + 1]]);
2298                             if ((delta1 < cETC1ColorDeltaMin) || (delta1 > cETC1ColorDeltaMax) || (delta2 < cETC1ColorDeltaMin) || (delta2 > cETC1ColorDeltaMax))
2299                             {
2300                                 if (*pTable == 0xFFFF)
2301                                     break;
2302                                 continue;
2303                             }
2304                         }
2305
2306                         const uint trial_error = rg_etc1::square(c_plus_delta - pColor[i]) + rg_etc1::square(p1 >> 8) + rg_etc1::square(p2 >> 8);
2307                         if (trial_error < best_error)
2308                         {
2309                             best_error = trial_error;
2310                             best_x = x;
2311                             best_packed_c1 = p1 & 0xFF;
2312                             best_packed_c2 = p2 & 0xFF;
2313                             best_i = i;
2314                             if (!best_error)
2315                                 goto found_perfect_match;
2316                         }
2317                     } while (*pTable != 0xFFFF);
2318                 }
2319             }
2320         found_perfect_match:
2321
2322             if (best_error == cUINT32_MAX)
2323                 return best_error;
2324
2325             best_error *= num_colors;
2326
2327             results.m_n = num_colors;
2328             results.m_block_color4 = !(best_x & 1);
2329             results.m_block_inten_table = (best_x >> 1) & 7;
2330             memset(results.m_pSelectors, (best_x >> 4) & 3, num_colors);
2331
2332             const uint best_packed_c0 = (best_x >> 8) & 255;
2333             results.m_block_color_unscaled[best_i] = static_cast<uint8>(best_packed_c0);
2334             results.m_block_color_unscaled[s_next_comp[best_i]] = static_cast<uint8>(best_packed_c1);
2335             results.m_block_color_unscaled[s_next_comp[best_i + 1]] = static_cast<uint8>(best_packed_c2);
2336             results.m_error = best_error;
2337
2338             return best_error;
2339         }
2340
2341         // Function originally from RYG's public domain real-time DXT1 compressor, modified for 555.
2342         static void dither_block_555(color_quad_u8 *dest, const color_quad_u8 *block)
2343         {
2344             int err[8], *ep1 = err, *ep2 = err + 4;
2345             uint8 *quant = g_quant5_tab + 8;
2346
2347             memset(dest, 0xFF, sizeof(color_quad_u8) * 16);
2348
2349             // process channels seperately
2350             for (int ch = 0; ch < 3; ch++)
2351             {
2352                 uint8 *bp = (uint8 *)block;
2353                 uint8 *dp = (uint8 *)dest;
2354
2355                 bp += ch;
2356                 dp += ch;
2357
2358                 memset(err, 0, sizeof(err));
2359                 for (int y = 0; y < 4; y++)
2360                 {
2361                     // pixel 0
2362                     dp[0] = quant[bp[0] + ((3 * ep2[1] + 5 * ep2[0]) >> 4)];
2363                     ep1[0] = bp[0] - dp[0];
2364
2365                     // pixel 1
2366                     dp[4] = quant[bp[4] + ((7 * ep1[0] + 3 * ep2[2] + 5 * ep2[1] + ep2[0]) >> 4)];
2367                     ep1[1] = bp[4] - dp[4];
2368
2369                     // pixel 2
2370                     dp[8] = quant[bp[8] + ((7 * ep1[1] + 3 * ep2[3] + 5 * ep2[2] + ep2[1]) >> 4)];
2371                     ep1[2] = bp[8] - dp[8];
2372
2373                     // pixel 3
2374                     dp[12] = quant[bp[12] + ((7 * ep1[2] + 5 * ep2[3] + ep2[2]) >> 4)];
2375                     ep1[3] = bp[12] - dp[12];
2376
2377                     // advance to next line
2378                     int *tmp = ep1;
2379                     ep1 = ep2;
2380                     ep2 = tmp;
2381                     bp += 16;
2382                     dp += 16;
2383                 }
2384             }
2385         }
2386
2387         unsigned int pack_etc1_block(void *pETC1_block, const unsigned int *pSrc_pixels_rgba, etc1_pack_params &pack_params)
2388         {
2389             const color_quad_u8 *pSrc_pixels = reinterpret_cast<const color_quad_u8 *>(pSrc_pixels_rgba);
2390             etc1_block &dst_block = *static_cast<etc1_block *>(pETC1_block);
2391
2392 #ifdef RG_ETC1_BUILD_DEBUG
2393             // Ensure all alpha values are 0xFF.
2394             for (uint i = 0; i < 16; i++)
2395             {
2396                 RG_ETC1_ASSERT(pSrc_pixels[i].a == 255);
2397             }
2398 #endif
2399
2400             color_quad_u8 src_pixel0(pSrc_pixels[0]);
2401
2402             // Check for solid block.
2403             const uint32 first_pixel_u32 = pSrc_pixels->m_u32;
2404             int r;
2405             for (r = 15; r >= 1; --r)
2406                 if (pSrc_pixels[r].m_u32 != first_pixel_u32)
2407                     break;
2408             if (!r)
2409                 return static_cast<unsigned int>(16 * pack_etc1_block_solid_color(dst_block, &pSrc_pixels[0].r, pack_params));
2410
2411             color_quad_u8 dithered_pixels[16];
2412             if (pack_params.m_dithering)
2413             {
2414                 dither_block_555(dithered_pixels, pSrc_pixels);
2415                 pSrc_pixels = dithered_pixels;
2416             }
2417
2418             etc1_optimizer optimizer;
2419
2420             uint64_t best_error = cUINT64_MAX;
2421             uint best_flip = false, best_use_color4 = false;
2422
2423             uint8 best_selectors[2][8];
2424             etc1_optimizer::results best_results[2];
2425             for (uint i = 0; i < 2; i++)
2426             {
2427                 best_results[i].m_n = 8;
2428                 best_results[i].m_pSelectors = best_selectors[i];
2429             }
2430
2431             uint8 selectors[3][8];
2432             etc1_optimizer::results results[3];
2433
2434             for (uint i = 0; i < 3; i++)
2435             {
2436                 results[i].m_n = 8;
2437                 results[i].m_pSelectors = selectors[i];
2438             }
2439
2440             color_quad_u8 subblock_pixels[8];
2441
2442             etc1_optimizer::params params(pack_params);
2443             params.m_num_src_pixels = 8;
2444             params.m_pSrc_pixels = subblock_pixels;
2445
2446             for (uint flip = 0; flip < 2; flip++)
2447             {
2448                 for (uint use_color4 = 0; use_color4 < 2; use_color4++)
2449                 {
2450                     uint64_t trial_error = 0;
2451
2452                     uint subblock;
2453                     for (subblock = 0; subblock < 2; subblock++)
2454                     {
2455                         if (flip)
2456                             memcpy(subblock_pixels, pSrc_pixels + subblock * 8, sizeof(color_quad_u8) * 8);
2457                         else
2458                         {
2459                             const color_quad_u8 *pSrc_col = pSrc_pixels + subblock * 2;
2460                             subblock_pixels[0] = pSrc_col[0];
2461                             subblock_pixels[1] = pSrc_col[4];
2462                             subblock_pixels[2] = pSrc_col[8];
2463                             subblock_pixels[3] = pSrc_col[12];
2464                             subblock_pixels[4] = pSrc_col[1];
2465                             subblock_pixels[5] = pSrc_col[5];
2466                             subblock_pixels[6] = pSrc_col[9];
2467                             subblock_pixels[7] = pSrc_col[13];
2468                         }
2469
2470                         results[2].m_error = cUINT64_MAX;
2471                         if ((params.m_quality >= cMediumQuality) && ((subblock) || (use_color4)))
2472                         {
2473                             const uint32 subblock_pixel0_u32 = subblock_pixels[0].m_u32;
2474                             for (r = 7; r >= 1; --r)
2475                                 if (subblock_pixels[r].m_u32 != subblock_pixel0_u32)
2476                                     break;
2477                             if (!r)
2478                             {
2479                                 pack_etc1_block_solid_color_constrained(results[2], 8, &subblock_pixels[0].r, pack_params, !use_color4, (subblock && !use_color4) ? &results[0].m_block_color_unscaled : NULL);
2480                             }
2481                         }
2482
2483                         params.m_use_color4 = (use_color4 != 0);
2484                         params.m_constrain_against_base_color5 = false;
2485
2486                         if ((!use_color4) && (subblock))
2487                         {
2488                             params.m_constrain_against_base_color5 = true;
2489                             params.m_base_color5 = results[0].m_block_color_unscaled;
2490                         }
2491
2492                         if (params.m_quality == cHighQuality)
2493                         {
2494                             static const int s_scan_delta_0_to_4[] = { -4, -3, -2, -1, 0, 1, 2, 3, 4 };
2495                             params.m_scan_delta_size = RG_ETC1_ARRAY_SIZE(s_scan_delta_0_to_4);
2496                             params.m_pScan_deltas = s_scan_delta_0_to_4;
2497                         }
2498                         else if (params.m_quality == cMediumQuality)
2499                         {
2500                             static const int s_scan_delta_0_to_1[] = { -1, 0, 1 };
2501                             params.m_scan_delta_size = RG_ETC1_ARRAY_SIZE(s_scan_delta_0_to_1);
2502                             params.m_pScan_deltas = s_scan_delta_0_to_1;
2503                         }
2504                         else
2505                         {
2506                             static const int s_scan_delta_0[] = { 0 };
2507                             params.m_scan_delta_size = RG_ETC1_ARRAY_SIZE(s_scan_delta_0);
2508                             params.m_pScan_deltas = s_scan_delta_0;
2509                         }
2510
2511                         optimizer.init(params, results[subblock]);
2512                         if (!optimizer.compute())
2513                             break;
2514
2515                         if (params.m_quality >= cMediumQuality)
2516                         {
2517                             // TODO: Fix fairly arbitrary/unrefined thresholds that control how far away to scan for potentially better solutions.
2518                             const uint refinement_error_thresh0 = 3000;
2519                             const uint refinement_error_thresh1 = 6000;
2520                             if (results[subblock].m_error > refinement_error_thresh0)
2521                             {
2522                                 if (params.m_quality == cMediumQuality)
2523                                 {
2524                                     static const int s_scan_delta_2_to_3[] = { -3, -2, 2, 3 };
2525                                     params.m_scan_delta_size = RG_ETC1_ARRAY_SIZE(s_scan_delta_2_to_3);
2526                                     params.m_pScan_deltas = s_scan_delta_2_to_3;
2527                                 }
2528                                 else
2529                                 {
2530                                     static const int s_scan_delta_5_to_5[] = { -5, 5 };
2531                                     static const int s_scan_delta_5_to_8[] = { -8, -7, -6, -5, 5, 6, 7, 8 };
2532                                     if (results[subblock].m_error > refinement_error_thresh1)
2533                                     {
2534                                         params.m_scan_delta_size = RG_ETC1_ARRAY_SIZE(s_scan_delta_5_to_8);
2535                                         params.m_pScan_deltas = s_scan_delta_5_to_8;
2536                                     }
2537                                     else
2538                                     {
2539                                         params.m_scan_delta_size = RG_ETC1_ARRAY_SIZE(s_scan_delta_5_to_5);
2540                                         params.m_pScan_deltas = s_scan_delta_5_to_5;
2541                                     }
2542                                 }
2543
2544                                 if (!optimizer.compute())
2545                                     break;
2546                             }
2547
2548                             if (results[2].m_error < results[subblock].m_error)
2549                                 results[subblock] = results[2];
2550                         }
2551
2552                         trial_error += results[subblock].m_error;
2553                         if (trial_error >= best_error)
2554                             break;
2555                     }
2556
2557                     if (subblock < 2)
2558                         continue;
2559
2560                     best_error = trial_error;
2561                     best_results[0] = results[0];
2562                     best_results[1] = results[1];
2563                     best_flip = flip;
2564                     best_use_color4 = use_color4;
2565
2566                 } // use_color4
2567
2568             } // flip
2569
2570             int dr = best_results[1].m_block_color_unscaled.r - best_results[0].m_block_color_unscaled.r;
2571             int dg = best_results[1].m_block_color_unscaled.g - best_results[0].m_block_color_unscaled.g;
2572             int db = best_results[1].m_block_color_unscaled.b - best_results[0].m_block_color_unscaled.b;
2573             RG_ETC1_ASSERT(best_use_color4 || ((rg_etc1::minimum(dr, dg, db) >= cETC1ColorDeltaMin) && (rg_etc1::maximum(dr, dg, db) <= cETC1ColorDeltaMax)));
2574
2575             if (best_use_color4)
2576             {
2577                 dst_block.m_bytes[0] = static_cast<uint8>(best_results[1].m_block_color_unscaled.r | (best_results[0].m_block_color_unscaled.r << 4));
2578                 dst_block.m_bytes[1] = static_cast<uint8>(best_results[1].m_block_color_unscaled.g | (best_results[0].m_block_color_unscaled.g << 4));
2579                 dst_block.m_bytes[2] = static_cast<uint8>(best_results[1].m_block_color_unscaled.b | (best_results[0].m_block_color_unscaled.b << 4));
2580             }
2581             else
2582             {
2583                 if (dr < 0)
2584                     dr += 8;
2585                 dst_block.m_bytes[0] = static_cast<uint8>((best_results[0].m_block_color_unscaled.r << 3) | dr);
2586                 if (dg < 0)
2587                     dg += 8;
2588                 dst_block.m_bytes[1] = static_cast<uint8>((best_results[0].m_block_color_unscaled.g << 3) | dg);
2589                 if (db < 0)
2590                     db += 8;
2591                 dst_block.m_bytes[2] = static_cast<uint8>((best_results[0].m_block_color_unscaled.b << 3) | db);
2592             }
2593
2594             dst_block.m_bytes[3] = static_cast<uint8>((best_results[1].m_block_inten_table << 2) | (best_results[0].m_block_inten_table << 5) | ((~best_use_color4 & 1) << 1) | best_flip);
2595
2596             uint selector0 = 0, selector1 = 0;
2597             if (best_flip)
2598             {
2599                 // flipped:
2600                 // { 0, 0 }, { 1, 0 }, { 2, 0 }, { 3, 0 },
2601                 // { 0, 1 }, { 1, 1 }, { 2, 1 }, { 3, 1 }
2602                 //
2603                 // { 0, 2 }, { 1, 2 }, { 2, 2 }, { 3, 2 },
2604                 // { 0, 3 }, { 1, 3 }, { 2, 3 }, { 3, 3 }
2605                 const uint8 *pSelectors0 = best_results[0].m_pSelectors;
2606                 const uint8 *pSelectors1 = best_results[1].m_pSelectors;
2607                 for (int x = 3; x >= 0; --x)
2608                 {
2609                     uint b;
2610                     b = g_selector_index_to_etc1[pSelectors1[4 + x]];
2611                     selector0 = (selector0 << 1) | (b & 1);
2612                     selector1 = (selector1 << 1) | (b >> 1);
2613
2614                     b = g_selector_index_to_etc1[pSelectors1[x]];
2615                     selector0 = (selector0 << 1) | (b & 1);
2616                     selector1 = (selector1 << 1) | (b >> 1);
2617
2618                     b = g_selector_index_to_etc1[pSelectors0[4 + x]];
2619                     selector0 = (selector0 << 1) | (b & 1);
2620                     selector1 = (selector1 << 1) | (b >> 1);
2621
2622                     b = g_selector_index_to_etc1[pSelectors0[x]];
2623                     selector0 = (selector0 << 1) | (b & 1);
2624                     selector1 = (selector1 << 1) | (b >> 1);
2625                 }
2626             }
2627             else
2628             {
2629                 // non-flipped:
2630                 // { 0, 0 }, { 0, 1 }, { 0, 2 }, { 0, 3 },
2631                 // { 1, 0 }, { 1, 1 }, { 1, 2 }, { 1, 3 }
2632                 //
2633                 // { 2, 0 }, { 2, 1 }, { 2, 2 }, { 2, 3 },
2634                 // { 3, 0 }, { 3, 1 }, { 3, 2 }, { 3, 3 }
2635                 for (int subblock = 1; subblock >= 0; --subblock)
2636                 {
2637                     const uint8 *pSelectors = best_results[subblock].m_pSelectors + 4;
2638                     for (uint i = 0; i < 2; i++)
2639                     {
2640                         uint b;
2641                         b = g_selector_index_to_etc1[pSelectors[3]];
2642                         selector0 = (selector0 << 1) | (b & 1);
2643                         selector1 = (selector1 << 1) | (b >> 1);
2644
2645                         b = g_selector_index_to_etc1[pSelectors[2]];
2646                         selector0 = (selector0 << 1) | (b & 1);
2647                         selector1 = (selector1 << 1) | (b >> 1);
2648
2649                         b = g_selector_index_to_etc1[pSelectors[1]];
2650                         selector0 = (selector0 << 1) | (b & 1);
2651                         selector1 = (selector1 << 1) | (b >> 1);
2652
2653                         b = g_selector_index_to_etc1[pSelectors[0]];
2654                         selector0 = (selector0 << 1) | (b & 1);
2655                         selector1 = (selector1 << 1) | (b >> 1);
2656
2657                         pSelectors -= 4;
2658                     }
2659                 }
2660             }
2661
2662             dst_block.m_bytes[4] = static_cast<uint8>(selector1 >> 8);
2663             dst_block.m_bytes[5] = static_cast<uint8>(selector1 & 0xFF);
2664             dst_block.m_bytes[6] = static_cast<uint8>(selector0 >> 8);
2665             dst_block.m_bytes[7] = static_cast<uint8>(selector0 & 0xFF);
2666
2667             return static_cast<unsigned int>(best_error);
2668         }
2669
2670     } // namespace rg_etc1
2671
2672 } // namespace vogl