1 | // Copyright 2011 Google Inc. All Rights Reserved. |
2 | // |
3 | // Use of this source code is governed by a BSD-style license |
4 | // that can be found in the COPYING file in the root of the source |
5 | // tree. An additional intellectual property rights grant can be found |
6 | // in the file PATENTS. All contributing project authors may |
7 | // be found in the AUTHORS file in the root of the source tree. |
8 | // ----------------------------------------------------------------------------- |
9 | // |
10 | // Alpha-plane compression. |
11 | // |
12 | // Author: Skal (pascal.massimino@gmail.com) |
13 | |
14 | #include <assert.h> |
15 | #include <stdlib.h> |
16 | |
17 | #include "src/enc/vp8i_enc.h" |
18 | #include "src/dsp/dsp.h" |
19 | #include "src/utils/filters_utils.h" |
20 | #include "src/utils/quant_levels_utils.h" |
21 | #include "src/utils/utils.h" |
22 | #include "src/webp/format_constants.h" |
23 | |
24 | // ----------------------------------------------------------------------------- |
25 | // Encodes the given alpha data via specified compression method 'method'. |
26 | // The pre-processing (quantization) is performed if 'quality' is less than 100. |
27 | // For such cases, the encoding is lossy. The valid range is [0, 100] for |
28 | // 'quality' and [0, 1] for 'method': |
29 | // 'method = 0' - No compression; |
30 | // 'method = 1' - Use lossless coder on the alpha plane only |
31 | // 'filter' values [0, 4] correspond to prediction modes none, horizontal, |
32 | // vertical & gradient filters. The prediction mode 4 will try all the |
33 | // prediction modes 0 to 3 and pick the best one. |
34 | // 'effort_level': specifies how much effort must be spent to try and reduce |
35 | // the compressed output size. In range 0 (quick) to 6 (slow). |
36 | // |
37 | // 'output' corresponds to the buffer containing compressed alpha data. |
38 | // This buffer is allocated by this method and caller should call |
39 | // WebPSafeFree(*output) when done. |
40 | // 'output_size' corresponds to size of this compressed alpha buffer. |
41 | // |
42 | // Returns 1 on successfully encoding the alpha and |
43 | // 0 if either: |
44 | // invalid quality or method, or |
45 | // memory allocation for the compressed data fails. |
46 | |
47 | #include "src/enc/vp8li_enc.h" |
48 | |
49 | static int EncodeLossless(const uint8_t* const data, int width, int height, |
50 | int effort_level, // in [0..6] range |
51 | int use_quality_100, VP8LBitWriter* const bw, |
52 | WebPAuxStats* const stats) { |
53 | int ok = 0; |
54 | WebPConfig config; |
55 | WebPPicture picture; |
56 | |
57 | WebPPictureInit(&picture); |
58 | picture.width = width; |
59 | picture.height = height; |
60 | picture.use_argb = 1; |
61 | picture.stats = stats; |
62 | if (!WebPPictureAlloc(&picture)) return 0; |
63 | |
64 | // Transfer the alpha values to the green channel. |
65 | WebPDispatchAlphaToGreen(data, width, picture.width, picture.height, |
66 | picture.argb, picture.argb_stride); |
67 | |
68 | WebPConfigInit(&config); |
69 | config.lossless = 1; |
70 | // Enable exact, or it would alter RGB values of transparent alpha, which is |
71 | // normally OK but not here since we are not encoding the input image but an |
72 | // internal encoding-related image containing necessary exact information in |
73 | // RGB channels. |
74 | config.exact = 1; |
75 | config.method = effort_level; // impact is very small |
76 | // Set a low default quality for encoding alpha. Ensure that Alpha quality at |
77 | // lower methods (3 and below) is less than the threshold for triggering |
78 | // costly 'BackwardReferencesTraceBackwards'. |
79 | // If the alpha quality is set to 100 and the method to 6, allow for a high |
80 | // lossless quality to trigger the cruncher. |
81 | config.quality = |
82 | (use_quality_100 && effort_level == 6) ? 100 : 8.f * effort_level; |
83 | assert(config.quality >= 0 && config.quality <= 100.f); |
84 | |
85 | // TODO(urvang): Temporary fix to avoid generating images that trigger |
86 | // a decoder bug related to alpha with color cache. |
87 | // See: https://code.google.com/p/webp/issues/detail?id=239 |
88 | // Need to re-enable this later. |
89 | ok = (VP8LEncodeStream(&config, &picture, bw, 0 /*use_cache*/) == VP8_ENC_OK); |
90 | WebPPictureFree(&picture); |
91 | ok = ok && !bw->error_; |
92 | if (!ok) { |
93 | VP8LBitWriterWipeOut(bw); |
94 | return 0; |
95 | } |
96 | return 1; |
97 | } |
98 | |
99 | // ----------------------------------------------------------------------------- |
100 | |
101 | // Small struct to hold the result of a filter mode compression attempt. |
102 | typedef struct { |
103 | size_t score; |
104 | VP8BitWriter bw; |
105 | WebPAuxStats stats; |
106 | } FilterTrial; |
107 | |
108 | // This function always returns an initialized 'bw' object, even upon error. |
109 | static int EncodeAlphaInternal(const uint8_t* const data, int width, int height, |
110 | int method, int filter, int reduce_levels, |
111 | int effort_level, // in [0..6] range |
112 | uint8_t* const tmp_alpha, |
113 | FilterTrial* result) { |
114 | int ok = 0; |
115 | const uint8_t* alpha_src; |
116 | WebPFilterFunc filter_func; |
117 | uint8_t ; |
118 | const size_t data_size = width * height; |
119 | const uint8_t* output = NULL; |
120 | size_t output_size = 0; |
121 | VP8LBitWriter tmp_bw; |
122 | |
123 | assert((uint64_t)data_size == (uint64_t)width * height); // as per spec |
124 | assert(filter >= 0 && filter < WEBP_FILTER_LAST); |
125 | assert(method >= ALPHA_NO_COMPRESSION); |
126 | assert(method <= ALPHA_LOSSLESS_COMPRESSION); |
127 | assert(sizeof(header) == ALPHA_HEADER_LEN); |
128 | |
129 | filter_func = WebPFilters[filter]; |
130 | if (filter_func != NULL) { |
131 | filter_func(data, width, height, width, tmp_alpha); |
132 | alpha_src = tmp_alpha; |
133 | } else { |
134 | alpha_src = data; |
135 | } |
136 | |
137 | if (method != ALPHA_NO_COMPRESSION) { |
138 | ok = VP8LBitWriterInit(&tmp_bw, data_size >> 3); |
139 | ok = ok && EncodeLossless(alpha_src, width, height, effort_level, |
140 | !reduce_levels, &tmp_bw, &result->stats); |
141 | if (ok) { |
142 | output = VP8LBitWriterFinish(&tmp_bw); |
143 | output_size = VP8LBitWriterNumBytes(&tmp_bw); |
144 | if (output_size > data_size) { |
145 | // compressed size is larger than source! Revert to uncompressed mode. |
146 | method = ALPHA_NO_COMPRESSION; |
147 | VP8LBitWriterWipeOut(&tmp_bw); |
148 | } |
149 | } else { |
150 | VP8LBitWriterWipeOut(&tmp_bw); |
151 | return 0; |
152 | } |
153 | } |
154 | |
155 | if (method == ALPHA_NO_COMPRESSION) { |
156 | output = alpha_src; |
157 | output_size = data_size; |
158 | ok = 1; |
159 | } |
160 | |
161 | // Emit final result. |
162 | header = method | (filter << 2); |
163 | if (reduce_levels) header |= ALPHA_PREPROCESSED_LEVELS << 4; |
164 | |
165 | VP8BitWriterInit(&result->bw, ALPHA_HEADER_LEN + output_size); |
166 | ok = ok && VP8BitWriterAppend(&result->bw, &header, ALPHA_HEADER_LEN); |
167 | ok = ok && VP8BitWriterAppend(&result->bw, output, output_size); |
168 | |
169 | if (method != ALPHA_NO_COMPRESSION) { |
170 | VP8LBitWriterWipeOut(&tmp_bw); |
171 | } |
172 | ok = ok && !result->bw.error_; |
173 | result->score = VP8BitWriterSize(&result->bw); |
174 | return ok; |
175 | } |
176 | |
177 | // ----------------------------------------------------------------------------- |
178 | |
179 | static int GetNumColors(const uint8_t* data, int width, int height, |
180 | int stride) { |
181 | int j; |
182 | int colors = 0; |
183 | uint8_t color[256] = { 0 }; |
184 | |
185 | for (j = 0; j < height; ++j) { |
186 | int i; |
187 | const uint8_t* const p = data + j * stride; |
188 | for (i = 0; i < width; ++i) { |
189 | color[p[i]] = 1; |
190 | } |
191 | } |
192 | for (j = 0; j < 256; ++j) { |
193 | if (color[j] > 0) ++colors; |
194 | } |
195 | return colors; |
196 | } |
197 | |
198 | #define FILTER_TRY_NONE (1 << WEBP_FILTER_NONE) |
199 | #define FILTER_TRY_ALL ((1 << WEBP_FILTER_LAST) - 1) |
200 | |
201 | // Given the input 'filter' option, return an OR'd bit-set of filters to try. |
202 | static uint32_t GetFilterMap(const uint8_t* alpha, int width, int height, |
203 | int filter, int effort_level) { |
204 | uint32_t bit_map = 0U; |
205 | if (filter == WEBP_FILTER_FAST) { |
206 | // Quick estimate of the best candidate. |
207 | int try_filter_none = (effort_level > 3); |
208 | const int kMinColorsForFilterNone = 16; |
209 | const int kMaxColorsForFilterNone = 192; |
210 | const int num_colors = GetNumColors(alpha, width, height, width); |
211 | // For low number of colors, NONE yields better compression. |
212 | filter = (num_colors <= kMinColorsForFilterNone) |
213 | ? WEBP_FILTER_NONE |
214 | : WebPEstimateBestFilter(alpha, width, height, width); |
215 | bit_map |= 1 << filter; |
216 | // For large number of colors, try FILTER_NONE in addition to the best |
217 | // filter as well. |
218 | if (try_filter_none || num_colors > kMaxColorsForFilterNone) { |
219 | bit_map |= FILTER_TRY_NONE; |
220 | } |
221 | } else if (filter == WEBP_FILTER_NONE) { |
222 | bit_map = FILTER_TRY_NONE; |
223 | } else { // WEBP_FILTER_BEST -> try all |
224 | bit_map = FILTER_TRY_ALL; |
225 | } |
226 | return bit_map; |
227 | } |
228 | |
229 | static void InitFilterTrial(FilterTrial* const score) { |
230 | score->score = (size_t)~0U; |
231 | VP8BitWriterInit(&score->bw, 0); |
232 | } |
233 | |
234 | static int ApplyFiltersAndEncode(const uint8_t* alpha, int width, int height, |
235 | size_t data_size, int method, int filter, |
236 | int reduce_levels, int effort_level, |
237 | uint8_t** const output, |
238 | size_t* const output_size, |
239 | WebPAuxStats* const stats) { |
240 | int ok = 1; |
241 | FilterTrial best; |
242 | uint32_t try_map = |
243 | GetFilterMap(alpha, width, height, filter, effort_level); |
244 | InitFilterTrial(&best); |
245 | |
246 | if (try_map != FILTER_TRY_NONE) { |
247 | uint8_t* filtered_alpha = (uint8_t*)WebPSafeMalloc(1ULL, data_size); |
248 | if (filtered_alpha == NULL) return 0; |
249 | |
250 | for (filter = WEBP_FILTER_NONE; ok && try_map; ++filter, try_map >>= 1) { |
251 | if (try_map & 1) { |
252 | FilterTrial trial; |
253 | ok = EncodeAlphaInternal(alpha, width, height, method, filter, |
254 | reduce_levels, effort_level, filtered_alpha, |
255 | &trial); |
256 | if (ok && trial.score < best.score) { |
257 | VP8BitWriterWipeOut(&best.bw); |
258 | best = trial; |
259 | } else { |
260 | VP8BitWriterWipeOut(&trial.bw); |
261 | } |
262 | } |
263 | } |
264 | WebPSafeFree(filtered_alpha); |
265 | } else { |
266 | ok = EncodeAlphaInternal(alpha, width, height, method, WEBP_FILTER_NONE, |
267 | reduce_levels, effort_level, NULL, &best); |
268 | } |
269 | if (ok) { |
270 | #if !defined(WEBP_DISABLE_STATS) |
271 | if (stats != NULL) { |
272 | stats->lossless_features = best.stats.lossless_features; |
273 | stats->histogram_bits = best.stats.histogram_bits; |
274 | stats->transform_bits = best.stats.transform_bits; |
275 | stats->cache_bits = best.stats.cache_bits; |
276 | stats->palette_size = best.stats.palette_size; |
277 | stats->lossless_size = best.stats.lossless_size; |
278 | stats->lossless_hdr_size = best.stats.lossless_hdr_size; |
279 | stats->lossless_data_size = best.stats.lossless_data_size; |
280 | } |
281 | #else |
282 | (void)stats; |
283 | #endif |
284 | *output_size = VP8BitWriterSize(&best.bw); |
285 | *output = VP8BitWriterBuf(&best.bw); |
286 | } else { |
287 | VP8BitWriterWipeOut(&best.bw); |
288 | } |
289 | return ok; |
290 | } |
291 | |
292 | static int EncodeAlpha(VP8Encoder* const enc, |
293 | int quality, int method, int filter, |
294 | int effort_level, |
295 | uint8_t** const output, size_t* const output_size) { |
296 | const WebPPicture* const pic = enc->pic_; |
297 | const int width = pic->width; |
298 | const int height = pic->height; |
299 | |
300 | uint8_t* quant_alpha = NULL; |
301 | const size_t data_size = width * height; |
302 | uint64_t sse = 0; |
303 | int ok = 1; |
304 | const int reduce_levels = (quality < 100); |
305 | |
306 | // quick sanity checks |
307 | assert((uint64_t)data_size == (uint64_t)width * height); // as per spec |
308 | assert(enc != NULL && pic != NULL && pic->a != NULL); |
309 | assert(output != NULL && output_size != NULL); |
310 | assert(width > 0 && height > 0); |
311 | assert(pic->a_stride >= width); |
312 | assert(filter >= WEBP_FILTER_NONE && filter <= WEBP_FILTER_FAST); |
313 | |
314 | if (quality < 0 || quality > 100) { |
315 | return 0; |
316 | } |
317 | |
318 | if (method < ALPHA_NO_COMPRESSION || method > ALPHA_LOSSLESS_COMPRESSION) { |
319 | return 0; |
320 | } |
321 | |
322 | if (method == ALPHA_NO_COMPRESSION) { |
323 | // Don't filter, as filtering will make no impact on compressed size. |
324 | filter = WEBP_FILTER_NONE; |
325 | } |
326 | |
327 | quant_alpha = (uint8_t*)WebPSafeMalloc(1ULL, data_size); |
328 | if (quant_alpha == NULL) { |
329 | return 0; |
330 | } |
331 | |
332 | // Extract alpha data (width x height) from raw_data (stride x height). |
333 | WebPCopyPlane(pic->a, pic->a_stride, quant_alpha, width, width, height); |
334 | |
335 | if (reduce_levels) { // No Quantization required for 'quality = 100'. |
336 | // 16 alpha levels gives quite a low MSE w.r.t original alpha plane hence |
337 | // mapped to moderate quality 70. Hence Quality:[0, 70] -> Levels:[2, 16] |
338 | // and Quality:]70, 100] -> Levels:]16, 256]. |
339 | const int alpha_levels = (quality <= 70) ? (2 + quality / 5) |
340 | : (16 + (quality - 70) * 8); |
341 | ok = QuantizeLevels(quant_alpha, width, height, alpha_levels, &sse); |
342 | } |
343 | |
344 | if (ok) { |
345 | VP8FiltersInit(); |
346 | ok = ApplyFiltersAndEncode(quant_alpha, width, height, data_size, method, |
347 | filter, reduce_levels, effort_level, output, |
348 | output_size, pic->stats); |
349 | #if !defined(WEBP_DISABLE_STATS) |
350 | if (pic->stats != NULL) { // need stats? |
351 | pic->stats->coded_size += (int)(*output_size); |
352 | enc->sse_[3] = sse; |
353 | } |
354 | #endif |
355 | } |
356 | |
357 | WebPSafeFree(quant_alpha); |
358 | return ok; |
359 | } |
360 | |
361 | //------------------------------------------------------------------------------ |
362 | // Main calls |
363 | |
364 | static int CompressAlphaJob(void* arg1, void* dummy) { |
365 | VP8Encoder* const enc = (VP8Encoder*)arg1; |
366 | const WebPConfig* config = enc->config_; |
367 | uint8_t* alpha_data = NULL; |
368 | size_t alpha_size = 0; |
369 | const int effort_level = config->method; // maps to [0..6] |
370 | const WEBP_FILTER_TYPE filter = |
371 | (config->alpha_filtering == 0) ? WEBP_FILTER_NONE : |
372 | (config->alpha_filtering == 1) ? WEBP_FILTER_FAST : |
373 | WEBP_FILTER_BEST; |
374 | if (!EncodeAlpha(enc, config->alpha_quality, config->alpha_compression, |
375 | filter, effort_level, &alpha_data, &alpha_size)) { |
376 | return 0; |
377 | } |
378 | if (alpha_size != (uint32_t)alpha_size) { // Sanity check. |
379 | WebPSafeFree(alpha_data); |
380 | return 0; |
381 | } |
382 | enc->alpha_data_size_ = (uint32_t)alpha_size; |
383 | enc->alpha_data_ = alpha_data; |
384 | (void)dummy; |
385 | return 1; |
386 | } |
387 | |
388 | void VP8EncInitAlpha(VP8Encoder* const enc) { |
389 | WebPInitAlphaProcessing(); |
390 | enc->has_alpha_ = WebPPictureHasTransparency(enc->pic_); |
391 | enc->alpha_data_ = NULL; |
392 | enc->alpha_data_size_ = 0; |
393 | if (enc->thread_level_ > 0) { |
394 | WebPWorker* const worker = &enc->alpha_worker_; |
395 | WebPGetWorkerInterface()->Init(worker); |
396 | worker->data1 = enc; |
397 | worker->data2 = NULL; |
398 | worker->hook = CompressAlphaJob; |
399 | } |
400 | } |
401 | |
402 | int VP8EncStartAlpha(VP8Encoder* const enc) { |
403 | if (enc->has_alpha_) { |
404 | if (enc->thread_level_ > 0) { |
405 | WebPWorker* const worker = &enc->alpha_worker_; |
406 | // Makes sure worker is good to go. |
407 | if (!WebPGetWorkerInterface()->Reset(worker)) { |
408 | return 0; |
409 | } |
410 | WebPGetWorkerInterface()->Launch(worker); |
411 | return 1; |
412 | } else { |
413 | return CompressAlphaJob(enc, NULL); // just do the job right away |
414 | } |
415 | } |
416 | return 1; |
417 | } |
418 | |
419 | int VP8EncFinishAlpha(VP8Encoder* const enc) { |
420 | if (enc->has_alpha_) { |
421 | if (enc->thread_level_ > 0) { |
422 | WebPWorker* const worker = &enc->alpha_worker_; |
423 | if (!WebPGetWorkerInterface()->Sync(worker)) return 0; // error |
424 | } |
425 | } |
426 | return WebPReportProgress(enc->pic_, enc->percent_ + 20, &enc->percent_); |
427 | } |
428 | |
429 | int VP8EncDeleteAlpha(VP8Encoder* const enc) { |
430 | int ok = 1; |
431 | if (enc->thread_level_ > 0) { |
432 | WebPWorker* const worker = &enc->alpha_worker_; |
433 | // finish anything left in flight |
434 | ok = WebPGetWorkerInterface()->Sync(worker); |
435 | // still need to end the worker, even if !ok |
436 | WebPGetWorkerInterface()->End(worker); |
437 | } |
438 | WebPSafeFree(enc->alpha_data_); |
439 | enc->alpha_data_ = NULL; |
440 | enc->alpha_data_size_ = 0; |
441 | enc->has_alpha_ = 0; |
442 | return ok; |
443 | } |
444 | |