Add a preliminary R11 EAC compressor

R=robertphillips@google.com

Author: krajcevski@google.com

Review URL: https://codereview.chromium.org/358973004

2 files changed, 261 insertions, 48 deletions

diff --git a/src/utils/SkTextureCompressor.cpp b/src/utils/SkTextureCompressor.cpp
index 3a7fcfb1d2..52bf09afb8 100644
--- a/src/utils/SkTextureCompressor.cpp
+++ b/src/utils/SkTextureCompressor.cpp
@@ -23,6 +23,47 @@ template <typename T> inline T abs_diff(const T &a, const T &b) {
     return (a > b) ? (a - b) : (b - a);
 }
 
+static bool is_extremal(uint8_t pixel) {
+    return 0 == pixel || 255 == pixel;
+}
+
+typedef uint64_t (*A84x4To64BitProc)(const uint8_t block[]);
+
+// This function is used by both R11 EAC and LATC to compress 4x4 blocks
+// of 8-bit alpha into 64-bit values that comprise the compressed data.
+// For both formats, we need to make sure that the dimensions of the 
+// src pixels are divisible by 4, and copy 4x4 blocks one at a time
+// for compression.
+static bool compress_4x4_a8_to_64bit(uint8_t* dst, const uint8_t* src,
+                                     int width, int height, int rowBytes,
+                                     A84x4To64BitProc proc) {
+    // Make sure that our data is well-formed enough to be considered for compression
+    if (0 == width || 0 == height || (width % 4) != 0 || (height % 4) != 0) {
+        return false;
+    }
+
+    int blocksX = width >> 2;
+    int blocksY = height >> 2;
+
+    uint8_t block[16];
+    uint64_t* encPtr = reinterpret_cast<uint64_t*>(dst);
+    for (int y = 0; y < blocksY; ++y) {
+        for (int x = 0; x < blocksX; ++x) {
+            // Load block
+            for (int k = 0; k < 4; ++k) {
+                memcpy(block + k*4, src + k*rowBytes + 4*x, 4);
+            }
+
+            // Compress it
+            *encPtr = proc(block);
+            ++encPtr;
+        }
+        src += 4 * rowBytes;
+    }
+
+    return true;
+}
+
 ////////////////////////////////////////////////////////////////////////////////
 //
 // LATC compressor
@@ -30,9 +71,9 @@ template <typename T> inline T abs_diff(const T &a, const T &b) {
 ////////////////////////////////////////////////////////////////////////////////
 
 // LATC compressed texels down into square 4x4 blocks
-static const int kPaletteSize = 8;
+static const int kLATCPaletteSize = 8;
 static const int kLATCBlockSize = 4;
-static const int kPixelsPerBlock = kLATCBlockSize * kLATCBlockSize;
+static const int kLATCPixelsPerBlock = kLATCBlockSize * kLATCBlockSize;
 
 // Generates an LATC palette. LATC constructs
 // a palette of eight colors from LUM0 and LUM1 using the algorithm:
@@ -55,7 +96,7 @@ static const int kPixelsPerBlock = kLATCBlockSize * kLATCBlockSize;
 // 0,                 if lum0 <= lum1 and code(x,y) == 6
 // 255,               if lum0 <= lum1 and code(x,y) == 7
 
-static void generate_palette(uint8_t palette[], uint8_t lum0, uint8_t lum1) {
+static void generate_latc_palette(uint8_t palette[], uint8_t lum0, uint8_t lum1) {
     palette[0] = lum0;
     palette[1] = lum1;
     if (lum0 > lum1) {
@@ -71,17 +112,13 @@ static void generate_palette(uint8_t palette[], uint8_t lum0, uint8_t lum1) {
     }
 }
 
-static bool is_extremal(uint8_t pixel) {
-    return 0 == pixel || 255 == pixel;
-}
-
 // Compress a block by using the bounding box of the pixels. It is assumed that
 // there are no extremal pixels in this block otherwise we would have used
 // compressBlockBBIgnoreExtremal.
-static uint64_t compress_block_bb(const uint8_t pixels[]) {
+static uint64_t compress_latc_block_bb(const uint8_t pixels[]) {
     uint8_t minVal = 255;
     uint8_t maxVal = 0;
-    for (int i = 0; i < kPixelsPerBlock; ++i) {
+    for (int i = 0; i < kLATCPixelsPerBlock; ++i) {
         minVal = SkTMin(pixels[i], minVal);
         maxVal = SkTMax(pixels[i], maxVal);
     }
@@ -89,16 +126,16 @@ static uint64_t compress_block_bb(const uint8_t pixels[]) {
     SkASSERT(!is_extremal(minVal));
     SkASSERT(!is_extremal(maxVal));
 
-    uint8_t palette[kPaletteSize];
-    generate_palette(palette, maxVal, minVal);
+    uint8_t palette[kLATCPaletteSize];
+    generate_latc_palette(palette, maxVal, minVal);
 
     uint64_t indices = 0;
-    for (int i = kPixelsPerBlock - 1; i >= 0; --i) {
+    for (int i = kLATCPixelsPerBlock - 1; i >= 0; --i) {
 
         // Find the best palette index
         uint8_t bestError = abs_diff(pixels[i], palette[0]);
         uint8_t idx = 0;
-        for (int j = 1; j < kPaletteSize; ++j) {
+        for (int j = 1; j < kLATCPaletteSize; ++j) {
             uint8_t error = abs_diff(pixels[i], palette[j]);
             if (error < bestError) {
                 bestError = error;
@@ -120,10 +157,10 @@ static uint64_t compress_block_bb(const uint8_t pixels[]) {
 // Compress a block by using the bounding box of the pixels without taking into
 // account the extremal values. The generated palette will contain extremal values
 // and fewer points along the line segment to interpolate.
-static uint64_t compress_block_bb_ignore_extremal(const uint8_t pixels[]) {
+static uint64_t compress_latc_block_bb_ignore_extremal(const uint8_t pixels[]) {
     uint8_t minVal = 255;
     uint8_t maxVal = 0;
-    for (int i = 0; i < kPixelsPerBlock; ++i) {
+    for (int i = 0; i < kLATCPixelsPerBlock; ++i) {
         if (is_extremal(pixels[i])) {
             continue;
         }
@@ -135,11 +172,11 @@ static uint64_t compress_block_bb_ignore_extremal(const uint8_t pixels[]) {
     SkASSERT(!is_extremal(minVal));
     SkASSERT(!is_extremal(maxVal));
 
-    uint8_t palette[kPaletteSize];
-    generate_palette(palette, minVal, maxVal);
+    uint8_t palette[kLATCPaletteSize];
+    generate_latc_palette(palette, minVal, maxVal);
 
     uint64_t indices = 0;
-    for (int i = kPixelsPerBlock - 1; i >= 0; --i) {
+    for (int i = kLATCPixelsPerBlock - 1; i >= 0; --i) {
 
         // Find the best palette index
         uint8_t idx = 0;
@@ -153,7 +190,7 @@ static uint64_t compress_block_bb_ignore_extremal(const uint8_t pixels[]) {
             }
         } else {
             uint8_t bestError = abs_diff(pixels[i], palette[0]);
-            for (int j = 1; j < kPaletteSize - 2; ++j) {
+            for (int j = 1; j < kLATCPaletteSize - 2; ++j) {
                 uint8_t error = abs_diff(pixels[i], palette[j]);
                 if (error < bestError) {
                     bestError = error;
@@ -170,7 +207,7 @@ static uint64_t compress_block_bb_ignore_extremal(const uint8_t pixels[]) {
         SkEndian_SwapLE64(
             static_cast<uint64_t>(minVal) |
             (static_cast<uint64_t>(maxVal) << 8) |
-            (indices << 16));        
+            (indices << 16));
 }
 
 
@@ -183,11 +220,11 @@ static uint64_t compress_block_bb_ignore_extremal(const uint8_t pixels[]) {
 // palette that has the extremal values built in. Otherwise, we use the full bounding
 // box.
 
-static uint64_t compress_block(const uint8_t pixels[]) {
+static uint64_t compress_latc_block(const uint8_t pixels[]) {
     // Collect unique pixels
     int nUniquePixels = 0;
-    uint8_t uniquePixels[kPixelsPerBlock];
-    for (int i = 0; i < kPixelsPerBlock; ++i) {
+    uint8_t uniquePixels[kLATCPixelsPerBlock];
+    for (int i = 0; i < kLATCPixelsPerBlock; ++i) {
         bool foundPixel = false;
         for (int j = 0; j < nUniquePixels; ++j) {
             foundPixel = foundPixel || uniquePixels[j] == pixels[i];
@@ -208,7 +245,7 @@ static uint64_t compress_block(const uint8_t pixels[]) {
     // with one or zero depending on which pixel they belong to.
     } else if (2 == nUniquePixels) {
         uint64_t outBlock = 0;
-        for (int i = kPixelsPerBlock - 1; i >= 0; --i) {
+        for (int i = kLATCPixelsPerBlock - 1; i >= 0; --i) {
             int idx = 0;
             if (pixels[i] == uniquePixels[1]) {
                 idx = 1;
@@ -237,42 +274,215 @@ static uint64_t compress_block(const uint8_t pixels[]) {
         // never take this step. We don't lose too much perf here because
         // most of the processing in this function is worth it for the 
         // 1 == nUniquePixels optimization.
-        return compress_block_bb(pixels);
+        return compress_latc_block_bb(pixels);
     } else {
-        return compress_block_bb_ignore_extremal(pixels);
+        return compress_latc_block_bb_ignore_extremal(pixels);
     }
 }
 
 static bool compress_a8_to_latc(uint8_t* dst, const uint8_t* src,
                                 int width, int height, int rowBytes) {
-    // Make sure that our data is well-formed enough to be
-    // considered for LATC compression
-    if (0 == width || 0 == height ||
-        (width % kLATCBlockSize) != 0 || (height % kLATCBlockSize) != 0) {
-        return false;
+    return compress_4x4_a8_to_64bit(dst, src, width, height, rowBytes, compress_latc_block);
+}
+
+////////////////////////////////////////////////////////////////////////////////
+//
+// R11 EAC Compressor
+//
+////////////////////////////////////////////////////////////////////////////////
+
+// Blocks compressed into R11 EAC are represented as follows:
+// 0000000000000000000000000000000000000000000000000000000000000000
+// |base_cw|mod|mul|  ----------------- indices -------------------
+//
+// To reconstruct the value of a given pixel, we use the formula:
+// clamp[0, 2047](base_cw * 8 + 4 + mod_val*mul*8)
+//
+// mod_val is chosen from a palette of values based on the index of the
+// given pixel. The palette is chosen by the value stored in mod.
+// This formula returns a value between 0 and 2047, which is converted
+// to a float from 0 to 1 in OpenGL.
+//
+// If mul is zero, then we set mul = 1/8, so that the formula becomes
+// clamp[0, 2047](base_cw * 8 + 4 + mod_val)
+
+static const int kNumR11EACPalettes = 16;
+static const int kR11EACPaletteSize = 8;
+static const int kR11EACModifierPalettes[kNumR11EACPalettes][kR11EACPaletteSize] = {
+    {-3, -6, -9, -15, 2, 5, 8, 14},
+    {-3, -7, -10, -13, 2, 6, 9, 12},
+    {-2, -5, -8, -13, 1, 4, 7, 12},
+    {-2, -4, -6, -13, 1, 3, 5, 12},
+    {-3, -6, -8, -12, 2, 5, 7, 11},
+    {-3, -7, -9, -11, 2, 6, 8, 10},
+    {-4, -7, -8, -11, 3, 6, 7, 10},
+    {-3, -5, -8, -11, 2, 4, 7, 10},
+    {-2, -6, -8, -10, 1, 5, 7, 9},
+    {-2, -5, -8, -10, 1, 4, 7, 9},
+    {-2, -4, -8, -10, 1, 3, 7, 9},
+    {-2, -5, -7, -10, 1, 4, 6, 9},
+    {-3, -4, -7, -10, 2, 3, 6, 9},
+    {-1, -2, -3, -10, 0, 1, 2, 9},
+    {-4, -6, -8, -9, 3, 5, 7, 8},
+    {-3, -5, -7, -9, 2, 4, 6, 8}
+};
+
+// Pack the base codeword, palette, and multiplier into the 64 bits necessary
+// to decode it.
+static uint64_t pack_r11eac_block(uint16_t base_cw, uint16_t palette, uint16_t multiplier,
+                                  uint64_t indices) {
+    SkASSERT(palette < 16);
+    SkASSERT(multiplier < 16);
+    SkASSERT(indices < (static_cast<uint64_t>(1) << 48));
+
+    const uint64_t b = static_cast<uint64_t>(base_cw) << 56;
+    const uint64_t m = static_cast<uint64_t>(multiplier) << 52;
+    const uint64_t p = static_cast<uint64_t>(palette) << 48;
+    return SkEndian_SwapBE64(b | m | p | indices);
+}
+
+// Given a base codeword, a modifier, and a multiplier, compute the proper
+// pixel value in the range [0, 2047].
+static uint16_t compute_r11eac_pixel(int base_cw, int modifier, int multiplier) {
+    int ret = (base_cw * 8 + 4) + (modifier * multiplier * 8);
+    return (ret > 2047)? 2047 : ((ret < 0)? 0 : ret);
+}
+
+// Compress a block into R11 EAC format.
+// The compression works as follows:
+// 1. Find the center of the span of the block's values. Use this as the base codeword.
+// 2. Choose a multiplier based roughly on the size of the span of block values
+// 3. Iterate through each palette and choose the one with the most accurate
+// modifiers.
+static uint64_t compress_heterogeneous_r11eac_block(const uint8_t block[16]) {
+    // Find the center of the data...
+    uint16_t bmin = block[0];
+    uint16_t bmax = block[0];
+    for (int i = 1; i < 16; ++i) {
+        bmin = SkTMin<uint16_t>(bmin, block[i]);
+        bmax = SkTMax<uint16_t>(bmax, block[i]);
     }
 
-    int blocksX = width / kLATCBlockSize;
-    int blocksY = height / kLATCBlockSize;
+    uint16_t center = (bmax + bmin) >> 1;
+    SkASSERT(center <= 255);
+
+    // Based on the min and max, we can guesstimate a proper multiplier
+    // This is kind of a magic choice to start with.
+    uint16_t multiplier = (bmax - center) / 10;
+
+    // Now convert the block to 11 bits and transpose it to match
+    // the proper layout
+    uint16_t cblock[16];
+    for (int i = 0; i < 4; ++i) {
+        for (int j = 0; j < 4; ++j) {
+            int srcIdx = i*4+j;
+            int dstIdx = j*4+i;
+            cblock[dstIdx] = (block[srcIdx] << 3) | (block[srcIdx] >> 5);
+        }
+    }
 
-    uint8_t block[16];
-    uint64_t* encPtr = reinterpret_cast<uint64_t*>(dst);
-    for (int y = 0; y < blocksY; ++y) {
-        for (int x = 0; x < blocksX; ++x) {
-            // Load block
-            static const int kBS = kLATCBlockSize;
-            for (int k = 0; k < kBS; ++k) {
-                memcpy(block + k*kBS, src + k*rowBytes + (kBS * x), kBS);
+    // Finally, choose the proper palette and indices
+    uint32_t bestError = static_cast<uint32_t>(-1);
+    uint64_t bestIndices = 0;
+    uint16_t bestPalette = 0;
+    for (uint16_t paletteIdx = 0; paletteIdx < kNumR11EACPalettes; ++paletteIdx) {
+        const int *palette = kR11EACModifierPalettes[paletteIdx];
+
+        // Iterate through each pixel to find the best palette index
+        // and update the indices with the choice. Also store the error
+        // for this palette to be compared against the best error...
+        uint32_t error = 0;
+        uint64_t indices = 0;
+        for (int pixelIdx = 0; pixelIdx < 16; ++pixelIdx) {
+            const uint16_t pixel = cblock[pixelIdx];
+
+            // Iterate through each palette value to find the best index
+            // for this particular pixel for this particular palette.
+            uint16_t bestPixelError =
+                abs_diff(pixel, compute_r11eac_pixel(center, palette[0], multiplier));
+            int bestIndex = 0;
+            for (int i = 1; i < kR11EACPaletteSize; ++i) {
+                const uint16_t p = compute_r11eac_pixel(center, palette[i], multiplier);
+                const uint16_t perror = abs_diff(pixel, p);
+
+                // Is this index better?
+                if (perror < bestPixelError) {
+                    bestIndex = i;
+                    bestPixelError = perror;
+                }
             }
 
-            // Compress it
-            *encPtr = compress_block(block);
-            ++encPtr;
+            SkASSERT(bestIndex < 8);
+
+            error += bestPixelError;
+            indices <<= 3;
+            indices |= bestIndex;
+        }
+
+        SkASSERT(indices < (static_cast<uint64_t>(1) << 48));
+
+        // Is this palette better?
+        if (error < bestError) {
+            bestPalette = paletteIdx;
+            bestIndices = indices;
+            bestError = error;
         }
-        src += kLATCBlockSize * rowBytes;
     }
 
-    return true;
+    // Finally, pack everything together...
+    return pack_r11eac_block(center, bestPalette, multiplier, bestIndices);
+}
+
+static uint64_t compress_r11eac_block(const uint8_t block[16]) {
+    // Are all blocks a solid color?
+    bool solid = true;
+    for (int i = 1; i < 16; ++i) {
+        if (block[i] != block[0]) {
+            solid = false;
+            break;
+        }
+    }
+
+    // Fully transparent? We know the encoding...
+    if (solid && 0 == block[0]) {
+        // (0x0060 << 48) produces the following:
+        // basw_cw: 0
+        // mod: 6, palette: {-4, -7, -8, -11, 3, 6, 7, 10}
+        // mod_val: -3
+        //
+        // this gives the following formula:
+        // clamp[0, 2047](0*8+4+(-4)) = 0
+        return SkEndian_SwapBE64(static_cast<uint64_t>(0x0060) << 48);
+
+    // Fully opaque? We know this encoding too...
+    } else if (solid && 255 == block[0]) {
+        // -1 produces the following:
+        // basw_cw: 255
+        // mod: 15, palette: {-3, -5, -7, -9, 2, 4, 6, 8}
+        // mod_val: 8
+        //
+        // this gives the following formula:
+        // clamp[0, 2047](255*8+4+8*8*8) = clamp[0, 2047](2556) = 2047
+        return static_cast<uint64_t>(-1);
+    }
+
+#if 0
+    else if (solid) {
+        // !TODO! krajcevski:
+        // This will probably never happen, since we're using this format
+        // primarily for compressing alpha maps. Usually the only
+        // non-fullly opaque or fully transparent blocks are not a solid
+        // intermediate color. If we notice that they are, then we can
+        // add another optimization...
+    }
+#endif
+
+    return compress_heterogeneous_r11eac_block(block);
+}
+
+static bool compress_a8_to_r11eac(uint8_t* dst, const uint8_t* src,
+                                  int width, int height, int rowBytes) {
+    return compress_4x4_a8_to_64bit(dst, src, width, height, rowBytes, compress_r11eac_block);
 }
 
 ////////////////////////////////////////////////////////////////////////////////
@@ -281,6 +491,7 @@ namespace SkTextureCompressor {
 
 static size_t get_compressed_data_size(Format fmt, int width, int height) {
     switch (fmt) {
+        case kR11_EAC_Format:
         case kLATC_Format:
         {
             // The LATC format is 64 bits per 4x4 block.
@@ -308,6 +519,7 @@ bool CompressBufferToFormat(uint8_t* dst, const uint8_t* src, SkColorType srcCol
     memset(kProcMap, 0, sizeof(kProcMap));
 
     kProcMap[kLATC_Format][kAlpha_8_SkColorType] = compress_a8_to_latc;
+    kProcMap[kR11_EAC_Format][kAlpha_8_SkColorType] = compress_a8_to_r11eac;
     
     CompressBitmapProc proc = kProcMap[format][srcColorType];
     if (NULL != proc) {
diff --git a/src/utils/SkTextureCompressor.h b/src/utils/SkTextureCompressor.h
index 7dda66b088..35b9b86430 100644
--- a/src/utils/SkTextureCompressor.h
+++ b/src/utils/SkTextureCompressor.h
@@ -16,10 +16,11 @@ class SkData;
 namespace SkTextureCompressor {
     // Various texture compression formats that we support.
     enum Format {
-        // Alpha only format.
+        // Alpha only formats.
         kLATC_Format,
+        kR11_EAC_Format,
 
-        kLast_Format = kLATC_Format
+        kLast_Format = kR11_EAC_Format
     };
     static const int kFormatCnt = kLast_Format + 1;