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