Add texture compression utility
R=robertphillips@google.com, egdaniel@google.com, halcanary@google.com, scroggo@google.com, reed@google.com
Author: krajcevski@google.com
Review URL: https://codereview.chromium.org/325733004
diff --git a/gyp/utils.gypi b/gyp/utils.gypi
index 3a94cc3..3097446 100644
--- a/gyp/utils.gypi
+++ b/gyp/utils.gypi
@@ -83,6 +83,8 @@
'<(skia_src_path)/utils/SkSHA1.cpp',
'<(skia_src_path)/utils/SkSHA1.h',
'<(skia_src_path)/utils/SkRTConf.cpp',
+ '<(skia_src_path)/utils/SkTextureCompressor.cpp',
+ '<(skia_src_path)/utils/SkTextureCompressor.h',
'<(skia_src_path)/utils/SkThreadUtils.h',
'<(skia_src_path)/utils/SkThreadUtils_pthread.cpp',
'<(skia_src_path)/utils/SkThreadUtils_pthread.h',
diff --git a/src/utils/SkTextureCompressor.cpp b/src/utils/SkTextureCompressor.cpp
new file mode 100644
index 0000000..adbaef6
--- /dev/null
+++ b/src/utils/SkTextureCompressor.cpp
@@ -0,0 +1,208 @@
+/*
+ * 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
+//
+////////////////////////////////////////////////////////////////////////////////
+
+// Absolute difference between two values. More correct than SkTAbs(a - b)
+// because it works on unsigned values.
+template <typename T> inline T abs_diff(const T &a, const T &b) {
+ return (a > b) ? (a - b) : (b - a);
+}
+
+////////////////////////////////////////////////////////////////////////////////
+//
+// LATC compressor
+//
+////////////////////////////////////////////////////////////////////////////////
+
+// Return the squared minimum error cost of approximating 'pixel' using the
+// provided palette. Return this in the middle 16 bits of the integer. Return
+// the best index in the palette for this pixel in the bottom 8 bits.
+static uint32_t compute_error(uint8_t pixel, uint8_t palette[8]) {
+ int minIndex = 0;
+ uint8_t error = abs_diff(palette[0], pixel);
+ for (int i = 1; i < 8; ++i) {
+ uint8_t diff = abs_diff(palette[i], pixel);
+ if (diff < error) {
+ minIndex = i;
+ error = diff;
+ }
+ }
+ uint16_t errSq = static_cast<uint16_t>(error) * static_cast<uint16_t>(error);
+ SkASSERT(minIndex >= 0 && minIndex < 8);
+ return (static_cast<uint32_t>(errSq) << 8) | static_cast<uint32_t>(minIndex);
+}
+
+// Compress LATC block. Each 4x4 block of pixels is decompressed by LATC from two
+// values LUM0 and LUM1, and an index into the generated palette. LATC constructs
+// a palette of eight colors from LUM0 and LUM1 using the algorithm:
+//
+// LUM0, if lum0 > lum1 and code(x,y) == 0
+// LUM1, if lum0 > lum1 and code(x,y) == 1
+// (6*LUM0+ LUM1)/7, if lum0 > lum1 and code(x,y) == 2
+// (5*LUM0+2*LUM1)/7, if lum0 > lum1 and code(x,y) == 3
+// (4*LUM0+3*LUM1)/7, if lum0 > lum1 and code(x,y) == 4
+// (3*LUM0+4*LUM1)/7, if lum0 > lum1 and code(x,y) == 5
+// (2*LUM0+5*LUM1)/7, if lum0 > lum1 and code(x,y) == 6
+// ( LUM0+6*LUM1)/7, if lum0 > lum1 and code(x,y) == 7
+//
+// LUM0, if lum0 <= lum1 and code(x,y) == 0
+// LUM1, if lum0 <= lum1 and code(x,y) == 1
+// (4*LUM0+ LUM1)/5, if lum0 <= lum1 and code(x,y) == 2
+// (3*LUM0+2*LUM1)/5, if lum0 <= lum1 and code(x,y) == 3
+// (2*LUM0+3*LUM1)/5, if lum0 <= lum1 and code(x,y) == 4
+// ( LUM0+4*LUM1)/5, if lum0 <= lum1 and code(x,y) == 5
+// 0, if lum0 <= lum1 and code(x,y) == 6
+// 255, if lum0 <= lum1 and code(x,y) == 7
+//
+// We compute the LATC palette using the following simple algorithm:
+// 1. Choose the minimum and maximum values in the block as LUM0 and LUM1
+// 2. Figure out which of the two possible palettes is better.
+
+static uint64_t compress_latc_block(uint8_t block[16]) {
+ // Just do a simple min/max but choose 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];
+
+ // Straight linear ramp
+ 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;
+ }
+
+ // Smaller linear ramp with min and max byte values at the end.
+ 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;
+
+ // Figure out which of the two is better:
+ // - accumError holds the accumulated error for each pixel from
+ // the associated palette
+ // - indices holds the best indices for each palette in the
+ // bottom 48 (16*3) bits.
+ uint32_t accumError[2] = { 0, 0 };
+ uint64_t indices[2] = { 0, 0 };
+ for (int i = 15; i >= 0; ++i) {
+ // For each palette:
+ // 1. Retreive the result of this pixel
+ // 2. Store the error in accumError
+ // 3. Store the minimum palette index in indices.
+ for (int p = 0; p < 2; ++p) {
+ uint32_t result = compute_error(block[i], palettes[p]);
+ accumError[p] += (result >> 8);
+ indices[p] <<= 3;
+ indices[p] |= result & ~7;
+ }
+ }
+
+ SkASSERT(indices[0] < (static_cast<uint64_t>(1) << 48));
+ SkASSERT(indices[1] < (static_cast<uint64_t>(1) << 48));
+
+ uint8_t paletteIdx = (accumError[0] > accumError[1]) ? 0 : 1;
+
+ // Assemble the compressed block.
+ uint64_t result = 0;
+
+ // Jam the first two palette entries into the bottom 16 bits of
+ // a 64 bit integer. Based on the palette that we chose, one will
+ // be larger than the other and it will select the proper palette.
+ result |= static_cast<uint64_t>(palettes[paletteIdx][0]);
+ result |= static_cast<uint64_t>(palettes[paletteIdx][1]) << 8;
+
+ // Jam the indices into the top 48 bits.
+ result |= indices[paletteIdx] << 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.colorType() != kAlpha_8_SkColorType)) {
+ 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 *CompressBitmapToFormat(const SkBitmap &bitmap, Format format) {
+ CompressBitmapProc kProcMap[kLastEnum_SkColorType + 1][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.colorType()][format];
+ if (NULL != proc) {
+ return proc(bitmap);
+ }
+
+ return NULL;
+}
+
+} // namespace SkTextureCompressor
diff --git a/src/utils/SkTextureCompressor.h b/src/utils/SkTextureCompressor.h
new file mode 100644
index 0000000..38fb5ea
--- /dev/null
+++ b/src/utils/SkTextureCompressor.h
@@ -0,0 +1,31 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkTextureCompressor_DEFINED
+#define SkTextureCompressor_DEFINED
+
+class SkBitmap;
+class SkData;
+
+namespace SkTextureCompressor {
+ // Various texture compression formats that we support.
+ enum Format {
+ // Alpha only format.
+ kLATC_Format,
+
+ kLast_Format = kLATC_Format
+ };
+ static const int kFormatCnt = kLast_Format + 1;
+
+ // Returns an SkData holding a blob of compressed data that corresponds
+ // to the bitmap. If the bitmap colorType cannot be compressed using the
+ // associated format, then we return NULL. The caller is responsible for
+ // calling unref() on the returned data.
+ SkData* CompressBitmapToFormat(const SkBitmap& bitmap, Format format);
+}
+
+#endif