Add texture compression utility

src/utils/SkTextureCompressor.cpp

Index: src/utils/SkTextureCompressor.cpp
diff --git a/src/utils/SkTextureCompressor.cpp b/src/utils/SkTextureCompressor.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..7696f3107a65125aabc7188239906a040985b68d
--- /dev/null
+++ b/src/utils/SkTextureCompressor.cpp
@@ -0,0 +1,167 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkTextureCompressor.h"
+
+#include "SkBitmap.h"
+#include "SkData.h"
+#include "SkEndian.h"
+
+////////////////////////////////////////////////////////////////////////////////
+//
+// Utility Functions
+//
+////////////////////////////////////////////////////////////////////////////////
+

[robertphillips, 2014/06/09 19:50:18]

Maybe SkTAbsDiff in SkTypes.h ?

[krajcevski, 2014/06/09 20:39:34]

Done.

+template<typename T>
+static const T absolute_difference(const T& a, const T& b) {
+    return (a > b) ? (a - b) : (b - a);
+}
+
+////////////////////////////////////////////////////////////////////////////////
+//
+// LATC compressor
+//
+////////////////////////////////////////////////////////////////////////////////
+

[robertphillips, 2014/06/09 19:50:18]

static const int kLATCPaletteSize = 8; ?

// Return the squared minimum error cost of approximating 'pixel' using the
provided palette

[krajcevski, 2014/06/09 20:39:34]

Done.

+static uint16_t compute_error(uint16_t pixel, uint8_t palette[8]) {
+    uint16_t error = 65535;
+    for (int i = 0; i < 8; ++i) {
+        uint16_t diff = absolute_difference(static_cast<uint16_t>(palette[i]), pixel);
+        error = SkMin32(diff, error);
+    }
+    return error*error;
+}
+

[robertphillips, 2014/06/09 19:50:18]

// Maybe an overview of the compression algorithm ?

// This attempts a brute force compression of an LATC block by determining which
of two possible palettes represent it with the least error. ?

[krajcevski, 2014/06/09 20:39:34]

Done.

+static uint64_t compress_latc_block(uint8_t block[16]) {
+    // Just do a simple min/max but choose from which of the
+    // two palettes is better
+    uint8_t maxVal = 0;
+    uint8_t minVal = 255;
+    for (int i = 0; i < 16; ++i) {
+        maxVal = SkMax32(maxVal, block[i]);
+        minVal = SkMin32(minVal, block[i]);
+    }
+
+    // Generate palettes
+    uint8_t palettes[2][8];
+

[robertphillips, 2014/06/09 19:50:18]

// palette 0 is a straight up linear ramp between minVal and maxVal ?

[krajcevski, 2014/06/09 20:39:34]

Done.

+    palettes[0][0] = maxVal;
+    palettes[0][1] = minVal;
+    for (int i = 1; i < 7; ++i) {
+        palettes[0][i+1] = ((7-i)*maxVal + i*minVal) / 7;
+    }
+

[robertphillips, 2014/06/09 19:50:18]

// palette 1 is a shorter linear ramp between minVal and maxVal but includes 0
and 255 ?

Is this palette ever selected ?

[krajcevski, 2014/06/09 20:39:34]

The way this algorithm is set up, probably not. In general this palette is
probably better for alpha masks, since you can ignore min/max pixels and try to
optimize for the 1-2 non saturated colors that the AA computes.

+    palettes[1][0] = minVal;
+    palettes[1][1] = maxVal;
+    for (int i = 1; i < 5; ++i) {
+        palettes[1][i+1] = ((5-i)*maxVal + i*minVal) / 5;
+    }
+    palettes[1][6] = 0;
+    palettes[1][7] = 255;

[robertphillips, 2014/06/09 19:50:17]

The raster code only ever generates 16 different alpha values (it only does 4x4
super sampling). It seems this knowledge could be used to select a better
palette.

[krajcevski, 2014/06/09 20:39:34]

Yes, probably. I think that investigating better compression schemes is probably
good to do once all of the other plumbing is in place (texture cache, etc).

+

[robertphillips, 2014/06/09 19:50:18]

error0 & error1 to match palette numbering ?

[krajcevski, 2014/06/09 20:39:34]

Done.

+    // Figure out which of the two is better
+    uint16_t error1 = 0, error2 = 0;
+    for (int i = 0; i < 16; ++i) {
+        uint16_t pixel = static_cast<uint16_t>(block[i]);
+        error1 += compute_error(pixel, palettes[0]);
+        error2 += compute_error(pixel, palettes[1]);
+    }
+    uint8_t *palette = (error1 > error2) ? palettes[1] : palettes[0];
+
+    // Compress the chosen palette
+    uint64_t result = 0;

[robertphillips, 2014/06/09 19:50:18]

Is this jamming the right values in?

[krajcevski, 2014/06/09 20:39:34]

Yes, although I did have to double check.

+    result |= static_cast<uint64_t>(palette[0]);
+    result |= static_cast<uint64_t>(palette[1]) << 8;
+
+    uint64_t indices = 0;
+    for (int i = 15; i >= 0; --i) {
+        uint8_t pixel = block[i];
+
+        uint8_t minError = absolute_difference(pixel, palette[0]);
+        uint8_t minErrorIndex = 0;

[robertphillips, 2014/06/09 19:50:18]

So we essentially do this loop to select the palette. Can we store both then and
then just pick one?

[krajcevski, 2014/06/09 20:39:34]

The palette is selected in the preceding loop. This loop is to determine what
index into the palette to store for each pixel. I've added this as a comment.

+        for (int j = 1; j < 8; ++j) {
+            uint8_t error = absolute_difference(pixel, palette[j]);
+            if (error < minError) {
+                minError = error;
+                minErrorIndex = j;
+            }
+        }
+        SkASSERT(minErrorIndex < 8);
+
+        indices <<= 3;
+        indices |= minErrorIndex;
+    }
+    result |= indices << 16;
+
+    // We assume everything is little endian, if it's not then make it so.
+    return SkEndian_SwapLE64(result);
+}
+
+static SkData *compress_a8_to_latc(const SkBitmap &bm) {
+    // LATC compressed texels down into square 4x4 blocks
+    static const int kLATCBlockSize = 4;
+
+    // Make sure that our data is well-formed enough to be
+    // considered for LATC compression
+    if (bm.width() == 0 || bm.height() == 0 ||
+        (bm.width() % kLATCBlockSize) != 0 ||
+        (bm.height() % kLATCBlockSize) != 0 ||
+        (bm.config() != SkBitmap::kA8_Config)) {
+        return NULL;
+    }
+
+    // The LATC format is 64 bits per 4x4 block.
+    static const int kLATCEncodedBlockSize = 8;
+
+    int blocksX = bm.width() / kLATCBlockSize;
+    int blocksY = bm.height() / kLATCBlockSize;
+
+    int compressedDataSize = blocksX * blocksY * kLATCEncodedBlockSize;
+    uint64_t* dst = reinterpret_cast<uint64_t*>(sk_malloc_throw(compressedDataSize));
+
+    uint8_t block[16];
+    const uint8_t* row = reinterpret_cast<const uint8_t*>(bm.getPixels());
+    uint64_t* encPtr = dst;
+    for (int y = 0; y < blocksY; ++y) {
+        for (int x = 0; x < blocksX; ++x) {
+            memcpy(block, row + (kLATCBlockSize * x), 4);
+            memcpy(block + 4, row + bm.rowBytes() + (kLATCBlockSize * x), 4);
+            memcpy(block + 8, row + 2*bm.rowBytes() + (kLATCBlockSize * x), 4);
+            memcpy(block + 12, row + 3*bm.rowBytes() + (kLATCBlockSize * x), 4);
+
+            *encPtr = compress_latc_block(block);
+            ++encPtr;
+        }
+        row += kLATCBlockSize * bm.rowBytes();
+    }
+
+    return SkData::NewFromMalloc(dst, compressedDataSize);
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+namespace SkTextureCompressor {
+
+typedef SkData *(*CompressBitmapProc)(const SkBitmap &bitmap);
+
+SkData *CompressBitmapToConfig(const SkBitmap &bitmap, Format config) {
+    CompressBitmapProc kProcMap[SkBitmap::kConfigCount][kFormatCnt];
+    memset(kProcMap, 0, sizeof(kProcMap));
+
+    // Map available bitmap configs to compression functions
+    kProcMap[SkBitmap::kA8_Config][kLATC_Format] = compress_a8_to_latc;
+
+    CompressBitmapProc proc = kProcMap[bitmap.config()][config];
+    if (NULL != proc) {
+        return proc(bitmap);
+    }
+
+    return NULL;
+}
+
+}  // namespace SkTextureCompressor