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.
22template <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
33static const int kPaletteSize = 8;
34static const int kLATCBlockSize = 4;
35static 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
58static 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
74static 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.
81static 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.
123static 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
186static 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
246static 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
280namespace SkTextureCompressor {
281
282static 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
301typedef bool (*CompressBitmapProc)(uint8_t* dst, const uint8_t* src,
302                                   int width, int height, int rowBytes);
303
304bool 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
320SkData *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