1 /* 2 * Copyright 2014 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #include "SkTextureCompressor.h" 9 10 #include "SkBitmap.h" 11 #include "SkData.h" 12 #include "SkEndian.h" 13 14 //////////////////////////////////////////////////////////////////////////////// 15 // 16 // Utility Functions 17 // 18 //////////////////////////////////////////////////////////////////////////////// 19 20 // Absolute difference between two values. More correct than SkTAbs(a - b) 21 // because it works on unsigned values. 22 template <typename T> inline T abs_diff(const T &a, const T &b) { 23 return (a > b) ? (a - b) : (b - a); 24 } 25 26 //////////////////////////////////////////////////////////////////////////////// 27 // 28 // LATC compressor 29 // 30 //////////////////////////////////////////////////////////////////////////////// 31 32 // LATC compressed texels down into square 4x4 blocks 33 static const int kPaletteSize = 8; 34 static const int kLATCBlockSize = 4; 35 static const int kPixelsPerBlock = kLATCBlockSize * kLATCBlockSize; 36 37 // Generates an LATC palette. LATC constructs 38 // a palette of eight colors from LUM0 and LUM1 using the algorithm: 39 // 40 // LUM0, if lum0 > lum1 and code(x,y) == 0 41 // LUM1, if lum0 > lum1 and code(x,y) == 1 42 // (6*LUM0+ LUM1)/7, if lum0 > lum1 and code(x,y) == 2 43 // (5*LUM0+2*LUM1)/7, if lum0 > lum1 and code(x,y) == 3 44 // (4*LUM0+3*LUM1)/7, if lum0 > lum1 and code(x,y) == 4 45 // (3*LUM0+4*LUM1)/7, if lum0 > lum1 and code(x,y) == 5 46 // (2*LUM0+5*LUM1)/7, if lum0 > lum1 and code(x,y) == 6 47 // ( LUM0+6*LUM1)/7, if lum0 > lum1 and code(x,y) == 7 48 // 49 // LUM0, if lum0 <= lum1 and code(x,y) == 0 50 // LUM1, if lum0 <= lum1 and code(x,y) == 1 51 // (4*LUM0+ LUM1)/5, if lum0 <= lum1 and code(x,y) == 2 52 // (3*LUM0+2*LUM1)/5, if lum0 <= lum1 and code(x,y) == 3 53 // (2*LUM0+3*LUM1)/5, if lum0 <= lum1 and code(x,y) == 4 54 // ( LUM0+4*LUM1)/5, if lum0 <= lum1 and code(x,y) == 5 55 // 0, if lum0 <= lum1 and code(x,y) == 6 56 // 255, if lum0 <= lum1 and code(x,y) == 7 57 58 static void generate_palette(uint8_t palette[], uint8_t lum0, uint8_t lum1) { 59 palette[0] = lum0; 60 palette[1] = lum1; 61 if (lum0 > lum1) { 62 for (int i = 1; i < 7; i++) { 63 palette[i+1] = ((7-i)*lum0 + i*lum1) / 7; 64 } 65 } else { 66 for (int i = 1; i < 5; i++) { 67 palette[i+1] = ((5-i)*lum0 + i*lum1) / 5; 68 } 69 palette[6] = 0; 70 palette[7] = 255; 71 } 72 } 73 74 static bool is_extremal(uint8_t pixel) { 75 return 0 == pixel || 255 == pixel; 76 } 77 78 // Compress a block by using the bounding box of the pixels. It is assumed that 79 // there are no extremal pixels in this block otherwise we would have used 80 // compressBlockBBIgnoreExtremal. 81 static uint64_t compress_block_bb(const uint8_t pixels[]) { 82 uint8_t minVal = 255; 83 uint8_t maxVal = 0; 84 for (int i = 0; i < kPixelsPerBlock; ++i) { 85 minVal = SkTMin(pixels[i], minVal); 86 maxVal = SkTMax(pixels[i], maxVal); 87 } 88 89 SkASSERT(!is_extremal(minVal)); 90 SkASSERT(!is_extremal(maxVal)); 91 92 uint8_t palette[kPaletteSize]; 93 generate_palette(palette, maxVal, minVal); 94 95 uint64_t indices = 0; 96 for (int i = kPixelsPerBlock - 1; i >= 0; --i) { 97 98 // Find the best palette index 99 uint8_t bestError = abs_diff(pixels[i], palette[0]); 100 uint8_t idx = 0; 101 for (int j = 1; j < kPaletteSize; ++j) { 102 uint8_t error = abs_diff(pixels[i], palette[j]); 103 if (error < bestError) { 104 bestError = error; 105 idx = j; 106 } 107 } 108 109 indices <<= 3; 110 indices |= idx; 111 } 112 113 return 114 SkEndian_SwapLE64( 115 static_cast<uint64_t>(maxVal) | 116 (static_cast<uint64_t>(minVal) << 8) | 117 (indices << 16)); 118 } 119 120 // Compress a block by using the bounding box of the pixels without taking into 121 // account the extremal values. The generated palette will contain extremal values 122 // and fewer points along the line segment to interpolate. 123 static uint64_t compress_block_bb_ignore_extremal(const uint8_t pixels[]) { 124 uint8_t minVal = 255; 125 uint8_t maxVal = 0; 126 for (int i = 0; i < kPixelsPerBlock; ++i) { 127 if (is_extremal(pixels[i])) { 128 continue; 129 } 130 131 minVal = SkTMin(pixels[i], minVal); 132 maxVal = SkTMax(pixels[i], maxVal); 133 } 134 135 SkASSERT(!is_extremal(minVal)); 136 SkASSERT(!is_extremal(maxVal)); 137 138 uint8_t palette[kPaletteSize]; 139 generate_palette(palette, minVal, maxVal); 140 141 uint64_t indices = 0; 142 for (int i = kPixelsPerBlock - 1; i >= 0; --i) { 143 144 // Find the best palette index 145 uint8_t idx = 0; 146 if (is_extremal(pixels[i])) { 147 if (0xFF == pixels[i]) { 148 idx = 7; 149 } else if (0 == pixels[i]) { 150 idx = 6; 151 } else { 152 SkFAIL("Pixel is extremal but not really?!"); 153 } 154 } else { 155 uint8_t bestError = abs_diff(pixels[i], palette[0]); 156 for (int j = 1; j < kPaletteSize - 2; ++j) { 157 uint8_t error = abs_diff(pixels[i], palette[j]); 158 if (error < bestError) { 159 bestError = error; 160 idx = j; 161 } 162 } 163 } 164 165 indices <<= 3; 166 indices |= idx; 167 } 168 169 return 170 SkEndian_SwapLE64( 171 static_cast<uint64_t>(minVal) | 172 (static_cast<uint64_t>(maxVal) << 8) | 173 (indices << 16)); 174 } 175 176 177 // Compress LATC block. Each 4x4 block of pixels is decompressed by LATC from two 178 // values LUM0 and LUM1, and an index into the generated palette. Details of how 179 // the palette is generated can be found in the comments of generatePalette above. 180 // 181 // We choose which palette type to use based on whether or not 'pixels' contains 182 // any extremal values (0 or 255). If there are extremal values, then we use the 183 // palette that has the extremal values built in. Otherwise, we use the full bounding 184 // box. 185 186 static uint64_t compress_block(const uint8_t pixels[]) { 187 // Collect unique pixels 188 int nUniquePixels = 0; 189 uint8_t uniquePixels[kPixelsPerBlock]; 190 for (int i = 0; i < kPixelsPerBlock; ++i) { 191 bool foundPixel = false; 192 for (int j = 0; j < nUniquePixels; ++j) { 193 foundPixel = foundPixel || uniquePixels[j] == pixels[i]; 194 } 195 196 if (!foundPixel) { 197 uniquePixels[nUniquePixels] = pixels[i]; 198 ++nUniquePixels; 199 } 200 } 201 202 // If there's only one unique pixel, then our compression is easy. 203 if (1 == nUniquePixels) { 204 return SkEndian_SwapLE64(pixels[0] | (pixels[0] << 8)); 205 206 // Similarly, if there are only two unique pixels, then our compression is 207 // easy again: place the pixels in the block header, and assign the indices 208 // with one or zero depending on which pixel they belong to. 209 } else if (2 == nUniquePixels) { 210 uint64_t outBlock = 0; 211 for (int i = kPixelsPerBlock - 1; i >= 0; --i) { 212 int idx = 0; 213 if (pixels[i] == uniquePixels[1]) { 214 idx = 1; 215 } 216 217 outBlock <<= 3; 218 outBlock |= idx; 219 } 220 outBlock <<= 16; 221 outBlock |= (uniquePixels[0] | (uniquePixels[1] << 8)); 222 return SkEndian_SwapLE64(outBlock); 223 } 224 225 // Count non-maximal pixel values 226 int nonExtremalPixels = 0; 227 for (int i = 0; i < nUniquePixels; ++i) { 228 if (!is_extremal(uniquePixels[i])) { 229 ++nonExtremalPixels; 230 } 231 } 232 233 // If all the pixels are nonmaximal then compute the palette using 234 // the bounding box of all the pixels. 235 if (nonExtremalPixels == nUniquePixels) { 236 // This is really just for correctness, in all of my tests we 237 // never take this step. We don't lose too much perf here because 238 // most of the processing in this function is worth it for the 239 // 1 == nUniquePixels optimization. 240 return compress_block_bb(pixels); 241 } else { 242 return compress_block_bb_ignore_extremal(pixels); 243 } 244 } 245 246 static bool compress_a8_to_latc(uint8_t* dst, const uint8_t* src, 247 int width, int height, int rowBytes) { 248 // Make sure that our data is well-formed enough to be 249 // considered for LATC compression 250 if (0 == width || 0 == height || 251 (width % kLATCBlockSize) != 0 || (height % kLATCBlockSize) != 0) { 252 return false; 253 } 254 255 int blocksX = width / kLATCBlockSize; 256 int blocksY = height / kLATCBlockSize; 257 258 uint8_t block[16]; 259 uint64_t* encPtr = reinterpret_cast<uint64_t*>(dst); 260 for (int y = 0; y < blocksY; ++y) { 261 for (int x = 0; x < blocksX; ++x) { 262 // Load block 263 static const int kBS = kLATCBlockSize; 264 for (int k = 0; k < kBS; ++k) { 265 memcpy(block + k*kBS, src + k*rowBytes + (kBS * x), kBS); 266 } 267 268 // Compress it 269 *encPtr = compress_block(block); 270 ++encPtr; 271 } 272 src += kLATCBlockSize * rowBytes; 273 } 274 275 return true; 276 } 277 278 //////////////////////////////////////////////////////////////////////////////// 279 280 namespace SkTextureCompressor { 281 282 static size_t get_compressed_data_size(Format fmt, int width, int height) { 283 switch (fmt) { 284 case kLATC_Format: 285 { 286 // The LATC format is 64 bits per 4x4 block. 287 static const int kLATCEncodedBlockSize = 8; 288 289 int blocksX = width / kLATCBlockSize; 290 int blocksY = height / kLATCBlockSize; 291 292 return blocksX * blocksY * kLATCEncodedBlockSize; 293 } 294 295 default: 296 SkFAIL("Unknown compressed format!"); 297 return 0; 298 } 299 } 300 301 typedef bool (*CompressBitmapProc)(uint8_t* dst, const uint8_t* src, 302 int width, int height, int rowBytes); 303 304 bool CompressBufferToFormat(uint8_t* dst, const uint8_t* src, SkColorType srcColorType, 305 int width, int height, int rowBytes, Format format) { 306 307 CompressBitmapProc kProcMap[kFormatCnt][kLastEnum_SkColorType + 1]; 308 memset(kProcMap, 0, sizeof(kProcMap)); 309 310 kProcMap[kLATC_Format][kAlpha_8_SkColorType] = compress_a8_to_latc; 311 312 CompressBitmapProc proc = kProcMap[format][srcColorType]; 313 if (NULL != proc) { 314 return proc(dst, src, width, height, rowBytes); 315 } 316 317 return false; 318 } 319 320 SkData *CompressBitmapToFormat(const SkBitmap &bitmap, Format format) { 321 SkAutoLockPixels alp(bitmap); 322 323 int compressedDataSize = get_compressed_data_size(format, bitmap.width(), bitmap.height()); 324 const uint8_t* src = reinterpret_cast<const uint8_t*>(bitmap.getPixels()); 325 uint8_t* dst = reinterpret_cast<uint8_t*>(sk_malloc_throw(compressedDataSize)); 326 if (CompressBufferToFormat(dst, src, bitmap.colorType(), bitmap.width(), bitmap.height(), 327 bitmap.rowBytes(), format)) { 328 return SkData::NewFromMalloc(dst, compressedDataSize); 329 } 330 331 sk_free(dst); 332 return NULL; 333 } 334 335 } // namespace SkTextureCompressor 336