src/third_party/android_opengl/etc1/etc1.cpp

   1 // Copyright 2009 Google Inc.
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 // You may obtain a copy of the License at
   6 //
   7 //     http://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 // See the License for the specific language governing permissions and
  13 // limitations under the License.
  14
  15 // This is branched from frameworks/base/opengl/include/ETC1/etc1.cc
  16 //
  17 // It has been modified as follows:
  18 // 1. Unused or not related to encoding methods have been removed.
  19 // 2. Methods related to determining the size of the output texture have been
  20 //    added.
  21 // 3. EncodeImage has been modified to operate directly on a bitmap, work with
  22 //    4bpp input, and resize the output to a power-of-two size in order to work
  23 //    with the graphics driver.
  24 //
  25
  26 #include "etc1.h"
  27
  28 #include <string>
  29 #include <cmath>
  30
  31 /* From http://www.khronos.org/registry/gles/extensions/OES/OES_compressed_ETC1_RGB8_texture.txt
  32
  33  The number of bits that represent a 4x4 texel block is 64 bits if
  34  <internalformat> is given by ETC1_RGB8_OES.
  35
  36  The data for a block is a number of bytes,
  37
  38  {q0, q1, q2, q3, q4, q5, q6, q7}
  39
  40  where byte q0 is located at the lowest memory address and q7 at
  41  the highest. The 64 bits specifying the block is then represented
  42  by the following 64 bit integer:
  43
  44  int64bit = 256*(256*(256*(256*(256*(256*(256*q0+q1)+q2)+q3)+q4)+q5)+q6)+q7;
  45
  46  ETC1_RGB8_OES:
  47
  48  a) bit layout in bits 63 through 32 if diffbit = 0
  49
  50  63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48
  51  -----------------------------------------------
  52  | base col1 | base col2 | base col1 | base col2 |
  53  | R1 (4bits)| R2 (4bits)| G1 (4bits)| G2 (4bits)|
  54  -----------------------------------------------
  55
  56  47 46 45 44 43 42 41 40 39 38 37 36 35 34  33  32
  57  ---------------------------------------------------
  58  | base col1 | base col2 | table  | table  |diff|flip|
  59  | B1 (4bits)| B2 (4bits)| cw 1   | cw 2   |bit |bit |
  60  ---------------------------------------------------
  61
  62
  63  b) bit layout in bits 63 through 32 if diffbit = 1
  64
  65  63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48
  66  -----------------------------------------------
  67  | base col1    | dcol 2 | base col1    | dcol 2 |
  68  | R1' (5 bits) | dR2    | G1' (5 bits) | dG2    |
  69  -----------------------------------------------
  70
  71  47 46 45 44 43 42 41 40 39 38 37 36 35 34  33  32
  72  ---------------------------------------------------
  73  | base col 1   | dcol 2 | table  | table  |diff|flip|
  74  | B1' (5 bits) | dB2    | cw 1   | cw 2   |bit |bit |
  75  ---------------------------------------------------
  76
  77
  78  c) bit layout in bits 31 through 0 (in both cases)
  79
  80  31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16
  81  -----------------------------------------------
  82  |       most significant pixel index bits       |
  83  | p| o| n| m| l| k| j| i| h| g| f| e| d| c| b| a|
  84  -----------------------------------------------
  85
  86  15 14 13 12 11 10  9  8  7  6  5  4  3   2   1  0
  87  --------------------------------------------------
  88  |         least significant pixel index bits       |
  89  | p| o| n| m| l| k| j| i| h| g| f| e| d| c | b | a |
  90  --------------------------------------------------
  91
  92
  93  Add table 3.17.2: Intensity modifier sets for ETC1 compressed textures:
  94
  95  table codeword                modifier table
  96  ------------------        ----------------------
  97  0                     -8  -2  2   8
  98  1                    -17  -5  5  17
  99  2                    -29  -9  9  29
 100  3                    -42 -13 13  42
 101  4                    -60 -18 18  60
 102  5                    -80 -24 24  80
 103  6                   -106 -33 33 106
 104  7                   -183 -47 47 183
 105
 106
 107  Add table 3.17.3 Mapping from pixel index values to modifier values for
 108  ETC1 compressed textures:
 109
 110  pixel index value
 111  ---------------
 112  msb     lsb           resulting modifier value
 113  -----   -----          -------------------------
 114  1       1            -b (large negative value)
 115  1       0            -a (small negative value)
 116  0       0             a (small positive value)
 117  0       1             b (large positive value)
 118
 119
 120  */
 121
 122 #define ETC1_ENCODED_BLOCK_SIZE 8
 123 #define ETC1_DECODED_BLOCK_SIZE 48
 124
 125 namespace {
 126
 127 typedef unsigned char etc1_byte;
 128 typedef int etc1_bool;
 129 typedef unsigned int etc1_uint32;
 130
 131 static const int kModifierTable[] = {
 132 /* 0 */2, 8, -2, -8,
 133 /* 1 */5, 17, -5, -17,
 134 /* 2 */9, 29, -9, -29,
 135 /* 3 */13, 42, -13, -42,
 136 /* 4 */18, 60, -18, -60,
 137 /* 5 */24, 80, -24, -80,
 138 /* 6 */33, 106, -33, -106,
 139 /* 7 */47, 183, -47, -183 };
 140
 141
 142 static inline etc1_byte clamp(int x) {
 143     return (etc1_byte) (x >= 0 ? (x < 255 ? x : 255) : 0);
 144 }
 145
 146 static
 147 inline int convert4To8(int b) {
 148     int c = b & 0xf;
 149     return (c << 4) | c;
 150 }
 151
 152 static
 153 inline int convert5To8(int b) {
 154     int c = b & 0x1f;
 155     return (c << 3) | (c >> 2);
 156 }
 157
 158 static
 159 inline int convert6To8(int b) {
 160     int c = b & 0x3f;
 161     return (c << 2) | (c >> 4);
 162 }
 163
 164 static
 165 inline int divideBy255(int d) {
 166     return (d + 128 + (d >> 8)) >> 8;
 167 }
 168
 169 static
 170 inline int convert8To4(int b) {
 171     int c = b & 0xff;
 172     return divideBy255(c * 15);
 173 }
 174
 175 static
 176 inline int convert8To5(int b) {
 177     int c = b & 0xff;
 178     return divideBy255(c * 31);
 179 }
 180
 181 typedef struct {
 182     etc1_uint32 high;
 183     etc1_uint32 low;
 184     etc1_uint32 score; // Lower is more accurate
 185 } etc_compressed;
 186
 187 static
 188 inline void take_best(etc_compressed* a, const etc_compressed* b) {
 189     if (a->score > b->score) {
 190         *a = *b;
 191     }
 192 }
 193
 194 static
 195 void etc_average_colors_subblock(const etc1_byte* pIn, etc1_uint32 inMask,
 196         etc1_byte* pColors, bool flipped, bool second) {
 197     int r = 0;
 198     int g = 0;
 199     int b = 0;
 200
 201     if (flipped) {
 202         int by = 0;
 203         if (second) {
 204             by = 2;
 205         }
 206         for (int y = 0; y < 2; y++) {
 207             int yy = by + y;
 208             for (int x = 0; x < 4; x++) {
 209                 int i = x + 4 * yy;
 210                 if (inMask & (1 << i)) {
 211                     const etc1_byte* p = pIn + i * 3;
 212                     r += *(p++);
 213                     g += *(p++);
 214                     b += *(p++);
 215                 }
 216             }
 217         }
 218     } else {
 219         int bx = 0;
 220         if (second) {
 221             bx = 2;
 222         }
 223         for (int y = 0; y < 4; y++) {
 224             for (int x = 0; x < 2; x++) {
 225                 int xx = bx + x;
 226                 int i = xx + 4 * y;
 227                 if (inMask & (1 << i)) {
 228                     const etc1_byte* p = pIn + i * 3;
 229                     r += *(p++);
 230                     g += *(p++);
 231                     b += *(p++);
 232                 }
 233             }
 234         }
 235     }
 236     pColors[0] = (etc1_byte)((r + 4) >> 3);
 237     pColors[1] = (etc1_byte)((g + 4) >> 3);
 238     pColors[2] = (etc1_byte)((b + 4) >> 3);
 239 }
 240
 241 static
 242 inline int square(int x) {
 243     return x * x;
 244 }
 245
 246 static etc1_uint32 chooseModifier(const etc1_byte* pBaseColors,
 247         const etc1_byte* pIn, etc1_uint32 *pLow, int bitIndex,
 248         const int* pModifierTable) {
 249     etc1_uint32 bestScore = ~0;
 250     int bestIndex = 0;
 251     int pixelR = pIn[0];
 252     int pixelG = pIn[1];
 253     int pixelB = pIn[2];
 254     int r = pBaseColors[0];
 255     int g = pBaseColors[1];
 256     int b = pBaseColors[2];
 257     for (int i = 0; i < 4; i++) {
 258         int modifier = pModifierTable[i];
 259         int decodedG = clamp(g + modifier);
 260         etc1_uint32 score = (etc1_uint32) (6 * square(decodedG - pixelG));
 261         if (score >= bestScore) {
 262             continue;
 263         }
 264         int decodedR = clamp(r + modifier);
 265         score += (etc1_uint32) (3 * square(decodedR - pixelR));
 266         if (score >= bestScore) {
 267             continue;
 268         }
 269         int decodedB = clamp(b + modifier);
 270         score += (etc1_uint32) square(decodedB - pixelB);
 271         if (score < bestScore) {
 272             bestScore = score;
 273             bestIndex = i;
 274         }
 275     }
 276     etc1_uint32 lowMask = (((bestIndex >> 1) << 16) | (bestIndex & 1))
 277             << bitIndex;
 278     *pLow |= lowMask;
 279     return bestScore;
 280 }
 281
 282 static
 283 void etc_encode_subblock_helper(const etc1_byte* pIn, etc1_uint32 inMask,
 284         etc_compressed* pCompressed, bool flipped, bool second,
 285         const etc1_byte* pBaseColors, const int* pModifierTable) {
 286     int score = pCompressed->score;
 287     if (flipped) {
 288         int by = 0;
 289         if (second) {
 290             by = 2;
 291         }
 292         for (int y = 0; y < 2; y++) {
 293             int yy = by + y;
 294             for (int x = 0; x < 4; x++) {
 295                 int i = x + 4 * yy;
 296                 if (inMask & (1 << i)) {
 297                     score += chooseModifier(pBaseColors, pIn + i * 3,
 298                             &pCompressed->low, yy + x * 4, pModifierTable);
 299                 }
 300             }
 301         }
 302     } else {
 303         int bx = 0;
 304         if (second) {
 305             bx = 2;
 306         }
 307         for (int y = 0; y < 4; y++) {
 308             for (int x = 0; x < 2; x++) {
 309                 int xx = bx + x;
 310                 int i = xx + 4 * y;
 311                 if (inMask & (1 << i)) {
 312                     score += chooseModifier(pBaseColors, pIn + i * 3,
 313                             &pCompressed->low, y + xx * 4, pModifierTable);
 314                 }
 315             }
 316         }
 317     }
 318     pCompressed->score = score;
 319 }
 320
 321 static bool inRange4bitSigned(int color) {
 322     return color >= -4 && color <= 3;
 323 }
 324
 325 static void etc_encodeBaseColors(etc1_byte* pBaseColors,
 326         const etc1_byte* pColors, etc_compressed* pCompressed) {
 327     int r1, g1, b1, r2, g2, b2; // 8 bit base colors for sub-blocks
 328     bool differential;
 329     {
 330         int r51 = convert8To5(pColors[0]);
 331         int g51 = convert8To5(pColors[1]);
 332         int b51 = convert8To5(pColors[2]);
 333         int r52 = convert8To5(pColors[3]);
 334         int g52 = convert8To5(pColors[4]);
 335         int b52 = convert8To5(pColors[5]);
 336
 337         r1 = convert5To8(r51);
 338         g1 = convert5To8(g51);
 339         b1 = convert5To8(b51);
 340
 341         int dr = r52 - r51;
 342         int dg = g52 - g51;
 343         int db = b52 - b51;
 344
 345         differential = inRange4bitSigned(dr) && inRange4bitSigned(dg)
 346                 && inRange4bitSigned(db);
 347         if (differential) {
 348             r2 = convert5To8(r51 + dr);
 349             g2 = convert5To8(g51 + dg);
 350             b2 = convert5To8(b51 + db);
 351             pCompressed->high |= (r51 << 27) | ((7 & dr) << 24) | (g51 << 19)
 352                     | ((7 & dg) << 16) | (b51 << 11) | ((7 & db) << 8) | 2;
 353         }
 354     }
 355
 356     if (!differential) {
 357         int r41 = convert8To4(pColors[0]);
 358         int g41 = convert8To4(pColors[1]);
 359         int b41 = convert8To4(pColors[2]);
 360         int r42 = convert8To4(pColors[3]);
 361         int g42 = convert8To4(pColors[4]);
 362         int b42 = convert8To4(pColors[5]);
 363         r1 = convert4To8(r41);
 364         g1 = convert4To8(g41);
 365         b1 = convert4To8(b41);
 366         r2 = convert4To8(r42);
 367         g2 = convert4To8(g42);
 368         b2 = convert4To8(b42);
 369         pCompressed->high |= (r41 << 28) | (r42 << 24) | (g41 << 20) | (g42
 370                 << 16) | (b41 << 12) | (b42 << 8);
 371     }
 372     pBaseColors[0] = r1;
 373     pBaseColors[1] = g1;
 374     pBaseColors[2] = b1;
 375     pBaseColors[3] = r2;
 376     pBaseColors[4] = g2;
 377     pBaseColors[5] = b2;
 378 }
 379
 380 static
 381 void etc_encode_block_helper(const etc1_byte* pIn, etc1_uint32 inMask,
 382         const etc1_byte* pColors, etc_compressed* pCompressed, bool flipped) {
 383     pCompressed->score = ~0;
 384     pCompressed->high = (flipped ? 1 : 0);
 385     pCompressed->low = 0;
 386
 387     etc1_byte pBaseColors[6];
 388
 389     etc_encodeBaseColors(pBaseColors, pColors, pCompressed);
 390
 391     int originalHigh = pCompressed->high;
 392
 393     const int* pModifierTable = kModifierTable;
 394     for (int i = 0; i < 8; i++, pModifierTable += 4) {
 395         etc_compressed temp;
 396         temp.score = 0;
 397         temp.high = originalHigh | (i << 5);
 398         temp.low = 0;
 399         etc_encode_subblock_helper(pIn, inMask, &temp, flipped, false,
 400                 pBaseColors, pModifierTable);
 401         take_best(pCompressed, &temp);
 402     }
 403     pModifierTable = kModifierTable;
 404     etc_compressed firstHalf = *pCompressed;
 405     for (int i = 0; i < 8; i++, pModifierTable += 4) {
 406         etc_compressed temp;
 407         temp.score = firstHalf.score;
 408         temp.high = firstHalf.high | (i << 2);
 409         temp.low = firstHalf.low;
 410         etc_encode_subblock_helper(pIn, inMask, &temp, flipped, true,
 411                 pBaseColors + 3, pModifierTable);
 412         if (i == 0) {
 413             *pCompressed = temp;
 414         } else {
 415             take_best(pCompressed, &temp);
 416         }
 417     }
 418 }
 419
 420 static void writeBigEndian(etc1_byte* pOut, etc1_uint32 d) {
 421     pOut[0] = (etc1_byte)(d >> 24);
 422     pOut[1] = (etc1_byte)(d >> 16);
 423     pOut[2] = (etc1_byte)(d >> 8);
 424     pOut[3] = (etc1_byte) d;
 425 }
 426
 427 // Input is a 4 x 4 square of 3-byte pixels in form R, G, B
 428 // inmask is a 16-bit mask where bit (1 << (x + y * 4)) tells whether the corresponding (x,y)
 429 // pixel is valid or not. Invalid pixel color values are ignored when compressing.
 430 // Output is an ETC1 compressed version of the data.
 431
 432 static void etc1_encode_block(etc1_byte* pIn, int inMask, etc1_byte* pOut) {
 433     etc1_byte colors[6];
 434     etc1_byte flippedColors[6];
 435     etc_average_colors_subblock(pIn, inMask, colors, false, false);
 436     etc_average_colors_subblock(pIn, inMask, colors + 3, false, true);
 437     etc_average_colors_subblock(pIn, inMask, flippedColors, true, false);
 438     etc_average_colors_subblock(pIn, inMask, flippedColors + 3, true, true);
 439
 440     etc_compressed a, b;
 441     etc_encode_block_helper(pIn, inMask, colors, &a, false);
 442     etc_encode_block_helper(pIn, inMask, flippedColors, &b, true);
 443     take_best(&a, &b);
 444     writeBigEndian(pOut, a.high);
 445     writeBigEndian(pOut + 4, a.low);
 446 }
 447
 448 }  // anonymous namespace
 449
 450 // Return the size of the encoded image data.
 451
 452 etc1_uint32 etc1_get_encoded_data_size(etc1_uint32 width, etc1_uint32 height) {
 453   return (((width + 3) & ~3) * ((height + 3) & ~3)) >> 1;
 454 }
 455
 456 // Encode an entire image.
 457 // pIn - pointer to the image data. Formatted such that the Red component of
 458 //       pixel (x,y) is at pIn + pixelSize * x + stride * y + redOffset;
 459 // pOut - pointer to encoded data. Must be large enough to store entire encoded image.
 460 // Returns false if there was an error.
 461
 462 bool etc1_encode_image(const etc1_byte* pIn, etc1_uint32 width, etc1_uint32 height,
 463          etc1_uint32 pixelSize, etc1_uint32 stride, etc1_byte* pOut, etc1_uint32 outWidth,
 464          etc1_uint32 outHeight) {
 465     if (pixelSize < 2) {
 466           return false;
 467     }
 468     static const unsigned short kYMask[] = { 0x0, 0xf, 0xff, 0xfff, 0xffff };
 469     static const unsigned short kXMask[] = { 0x0, 0x1111, 0x3333, 0x7777,
 470             0xffff };
 471     etc1_byte block[ETC1_DECODED_BLOCK_SIZE];
 472     etc1_byte encoded[ETC1_ENCODED_BLOCK_SIZE];
 473
 474     etc1_uint32 encodedWidth = (outWidth + 3) & ~3;
 475     etc1_uint32 encodedHeight = (outHeight + 3) & ~3;
 476
 477     for (etc1_uint32 y = 0; y < encodedHeight; y += 4) {
 478         etc1_uint32 yEnd = outHeight - y;
 479         if (yEnd > 4) {
 480             yEnd = 4;
 481         }
 482         int ymask = kYMask[yEnd];
 483         for (etc1_uint32 x = 0; x < encodedWidth; x += 4) {
 484             etc1_uint32 xEnd = outWidth - x;
 485             if (xEnd > 4) {
 486                 xEnd = 4;
 487             }
 488             const int mask = ymask & kXMask[xEnd];
 489             // Shortcut to only encode blocks which overlap the input image.
 490             // The outside region will be undefined garbage.
 491             if (x < width && y < height) {
 492                 for (etc1_uint32 cy = 0; cy < yEnd; cy++) {
 493                     etc1_byte* q = block + (cy * 4) * 3;
 494                     const etc1_byte* p = pIn + pixelSize * x + stride * (y + cy);
 495                     if (y + cy < height) {
 496                         for (etc1_uint32 cx = 0; cx < xEnd; cx++) {
 497                             if (x + cx < width) {
 498                                 if (pixelSize == 4) {
 499                                     // RGBA_8888: Filter out the input's alpha channel.
 500                                     *q++ = p[0];
 501                                     *q++ = p[1];
 502                                     *q++ = p[2];
 503                                 } else {
 504                                     // RGB_565: Unpack input's 2 bytes to RGB.
 505                                     int pixel = (p[1] << 8) | p[0];
 506                                     *q++ = convert5To8(pixel >> 11);
 507                                     *q++ = convert6To8(pixel >> 5);
 508                                     *q++ = convert5To8(pixel);
 509                                 }
 510                                 p += pixelSize;
 511                             } else {
 512                                 // Out of bounds of the input image but within a
 513                                 // block that must be properly encoded, so pad
 514                                 // the original image with the last pixel.
 515                                 *(q + 0) = *(q - 3);
 516                                 *(q + 1) = *(q - 2);
 517                                 *(q + 2) = *(q - 1);
 518                                 q += 3;
 519                             }
 520                         }
 521                     } else {
 522                       // Out of bounds of the input image but within a
 523                       // block that must be properly encoded, so pad the
 524                       // original image with the last pixel.
 525                       *(q + 0) = *(q - 12);
 526                       *(q + 1) = *(q - 11);
 527                       *(q + 2) = *(q - 10);
 528                       q += 3;
 529                     }
 530                 }
 531                 etc1_encode_block(block, mask, encoded);
 532                 memcpy(pOut, encoded, sizeof(encoded));
 533             } else if (x == width && width > 0 && height > 0) {
 534                 // We need to extend the block right after to the last pixel of
 535                 // the source bitmap for the blending to work nicely.
 536                 for (etc1_uint32 cy = 0; cy < yEnd; cy++) {
 537                     etc1_byte* q = block + (cy * 4) * 3;
 538                     const etc1_byte* p = pIn + pixelSize * (width - 1) +
 539                             stride * std::min(y + cy, height - 1);
 540                     for (etc1_uint32 cx = 0; cx < xEnd; cx++) {
 541                         if (pixelSize == 4) {
 542                             // RGBA_8888: Filter out the input's alpha channel.
 543                             *q++ = p[0];
 544                             *q++ = p[1];
 545                             *q++ = p[2];
 546                         } else {
 547                             // RGB_565: Unpack input's 2 bytes to RGB.
 548                             int pixel = (p[1] << 8) | p[0];
 549                             *q++ = convert5To8(pixel >> 11);
 550                             *q++ = convert6To8(pixel >> 5);
 551                             *q++ = convert5To8(pixel);
 552                         }
 553                     }
 554                 }
 555                 etc1_encode_block(block, mask, encoded);
 556                 memcpy(pOut, encoded, sizeof(encoded));
 557             } else if (y == height && width > 0 && height > 0) {
 558                 // We need to extend the block right after to the last pixel of
 559                 // the source bitmap for the blending to work nicely.
 560                 for (etc1_uint32 cy = 0; cy < yEnd; cy++) {
 561                     etc1_byte* q = block + (cy * 4) * 3;
 562                     for (etc1_uint32 cx = 0; cx < xEnd; cx++) {
 563                         const etc1_byte* p = pIn +
 564                                 pixelSize * std::min(x + cx, width - 1) +
 565                                 stride * (height - 1);
 566                         if (pixelSize == 4) {
 567                             // RGBA_8888: Filter out the input's alpha channel.
 568                             *q++ = p[0];
 569                             *q++ = p[1];
 570                             *q++ = p[2];
 571                         } else {
 572                             // RGB_565: Unpack input's 2 bytes to RGB.
 573                             int pixel = (p[1] << 8) | p[0];
 574                             *q++ = convert5To8(pixel >> 11);
 575                             *q++ = convert6To8(pixel >> 5);
 576                             *q++ = convert5To8(pixel);
 577                         }
 578                     }
 579                 }
 580                 etc1_encode_block(block, mask, encoded);
 581                 memcpy(pOut, encoded, sizeof(encoded));
 582             } else {
 583                 memset(pOut, 0xFF, sizeof(encoded));
 584             }
 585             pOut += sizeof(encoded);
 586         }
 587     }
 588     return true;
 589 }